Description

小 D 开了个饮料连锁店，连锁店共有 $n$ 家，出售的饮料种类相同。为了促销，小 D 决定让每家连锁店开展赠送活动。具体来说，在第 $i$ 家店，顾客可以用 $a_i$ 个饮料瓶兑换到 $b_i$ 瓶饮料和 $1$ 个纪念币（注意不足 $a_i$ 个饮料瓶则不能兑换）。

一家店可以兑换多次，兑换得到的饮料瓶还可以继续用于兑换。

小 C 买了 $s$ 瓶饮料，他想知道用这 $s$ 瓶饮料最多可以兑换到多少个纪念币。

Input Format

从文件 store.in 中读入数据。

输入第一行为两个整数 $n,s$，分别表示连锁店的数量和小 C 的饮料瓶数。

接下来 $n$ 行，每行两个整数 $a_i,b_i$，描述第 $i$家饮料店的赠送活动。

Output Format

输出到文件 store.out 中。

输出一行一个整数，表示小 C 最多能兑换到的纪念币数量。若小 C 能兑换到无限多个纪念币，则输出 $−1$。

Sample

样例输入1

3 11
4 1
5 2
8 4

样例输出1

3

样例1解释

最多兑换到 $3$ 个纪念币。兑换过程如下：

（1）在第 $1$ 家店用 $4$ 瓶换 $1$ 瓶，此时剩 $11 − 4 + 1 = 8$ 瓶，有 $1$ 个纪念币；

（2）在第 $1$ 家店用 $4$ 瓶换 $1$ 瓶，此时剩 $8 − 4 + 1 = 5$ 瓶，有 $2$ 个纪念币；

（3）在第 $2$ 家店用 $5$ 瓶换 $2$ 瓶，此时剩 $5 − 5 + 2 = 2$ 瓶，有 $3$ 个纪念币；

剩余的饮料瓶无法在任何店兑换，因此最多兑换到 $3$ 个纪念币。

样例2

见选手目录下的 store/store2.in 与 store/store2.ans。

Hint

对于 $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}$ 。