【问题描述】

作为对勤勤恳恳工作的Bessie的奖励，约翰已经决定开始支付Bessie一个小的每周津贴。约翰有n（1<=n<=20)种币值的硬币，面值小的硬币总能整除面值较大的硬币。（比如说，币值有如下几种：1美分，5美分，10美分，50美分......），利用给定的这些硬币，他将要每周付给Bessie一定金额的钱C(1<=c<=100,000,000)。

请帮他计算出他最多能给Bessie发几周的津贴。

输入格式:

第一行：2个用空格隔开的整数：N和C

第2 - n+1行：每行两个整数表示一种币值的硬币。第一个整数V(1<=V<=100,000,000)，表示币值，第二个整数B(1<=B<=1,000,000)，表示约翰拥有的这种硬币的个数

样例输入（文件allow.in）：

3 6
10 1
1 100
5 120

输入说明：

约翰想要每周付给Bessie 6美分。他有1个10美分的硬币、100个1美分的硬币、120个5美分的硬币。

输出格式：

一行：一个整数，表示约翰付给Bessie津贴得最多的周数。

样例输出（文件allow.out）：

111

输出说明：

约翰可以第一周付给Bessie一个10美分的硬币，接着的10周每周付给Bessie 2个5美分硬币，接下来的100周每周付给Bessie一个1美分的硬币和1个5美分的硬币。共计111周。