题目描述

Cirno想要乘公交车去幻想乡各地游玩。乘坐一次公交的票价为\(C\)元，且不设找零。
幻想乡发行了\(N\)种面值的硬币，大面值必然是小面值的整数倍。
设第\(i\)种硬币的面值为\(V_i\)，Cirno带了该种硬币\(B_i\)枚。她不会找别人把大面值的硬币换成零钱，也就是说，她坐公交时可能会多付钱。请你编写程序，计算她最多可以用这些硬币坐多少次公交？

输入格式

每个测试文件含3～5组测试数据，以文件结束符（EOF）表示输入结束。
对于每组测试数据：
第一行是两个正整数\(N,C\)；
之后\(N\)行，第\(i\)行包含2个正整数\(V_i,B_i\)。
30%的数据：\(B_i \le 100\)
100%的数据：\(C \le 10^8, \quad V_i \le 10^8, \quad B_i \le 10^8\)。数据保证\(V_i\)两两不等。

输出格式

对于每组数据，输出一行表示答案。
答案保证\(\le 2 \times 10^9\)。

样例

input

3 6
10 1
1 100
5 120

output

111

限制

Time limit: 1 sec
Memory limit: 128 megabytes

来源

From PKU Online Judge