Description

小D开了个饮料连锁店，连锁店共有n家，出售的饮料种类相同。为了促销，小D决定让每家连锁店开展赠送活动。具体来说，在第i家店，顾客可以用ai个饮料瓶兑换到bi瓶饮料和1个纪念币（注意不足ai个饮料瓶则不能兑换）。一家店可以兑换多次，兑换得到的饮料还可以继续用于兑换。
小C买了s瓶饮料，他想知道用这s瓶饮料最多可以兑换到多少个纪念币。

Format

Input

输入文件名为store.in。
输入第一行为两个整数n,s,分别表示连锁店的数量和小C的饮料瓶数。
接下来n行，每行两个整数ai,bi，描述第i家饮料店的赠送活动。

Output

输出文件名为store.out。
输出一行一个整数，表示小C最多能兑换到的纪念币的数量。若小C能兑换到无限多个纪念币，则输出-1

Sample 1

Input

3 11 
4 1 
5 2 
8 4 

Output

3 

Limitation

1s, 524288KiB for each test case.
【输入输出样例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
【数据范围】
对于30%的数据，0<=n<=10, 0<=s<=20；
对于50%的数据，0<=n<=1000 ,0<=s<=100 000；
对于100%的数据，0<=n<=100 000 ,0<=s<=10^19 ,0<=ai<=10^19 ,0<=bi<=10^19。