题目描述

经过“漫长”的暑假，终于等到学校开学了，校门口的超市老板激动万分，为了庆祝这个日子，超市开展了 $n$ 项促销活动。第 $i$ 项活动为顾客可以用 $a_i$ 个饮料瓶兑换到 $b_i$ 瓶饮料和1包辣条（注意不足 $a_i$ 个饮料瓶则不能兑换）。

你可以兑换任意次，每次可以自行选择适用哪项活动，兑换到的饮料喝完后得到的饮料瓶还可以继续用于兑换。

机房吃神 CBC 同学现在有 $s$ 个饮料瓶，他想知道用这 $s$ 瓶饮料最多可以得到多少包辣条。

输入格式

输入第一行为两个整数 $n$ , $s$ ，分别表示活动的数量和CBC同学现有的饮料瓶数。接下来 $n$ 行，每行两个整数 $a_i$ , $b_i$ ，描述 $i$ 项活动。

输出一行一个整数，表示 CBC 同学最多可以得到的辣条数量。若可以得到无限多包辣条，则输出 $−1$ 。

对于 $30\%$ 的数据， $0 \le n \le 10，0 \le s \le 20$

对于 $50\%$ 的数据， $0 \le n \le 1000，0 \le s \le 100000$

对于 $100\%$ 的数据，$0 \le n \le 100000，0 \le s \le 10^{19}, 0 \le a_i \le 10^{19}, 0 \le b_i \le 10^{19}$