题目描述

作为对勤勤恳恳工作的贝茜的奖励，约翰已经决定开始支付贝茜一个小的每周津贴．

约翰有${n(1≤}$${N≤}$${20)}$种币值的硬币，面值小的硬币总能整除面值较大的硬币．比如说，币值有如下几种：${1}$美分，${5}$美分，${10}$ 美分，${50}$美分…

利用给定的这些硬币，他将要每周付给贝茜一定金额的津贴${C(1≤}$${C≤}$${10^8)}$．

请帮他计算出他最多能给贝茜发几周的津贴．

输入格式

第${1}$行：${2}$个用空格隔开的整数${n}$和${C.}$

第${2}$到${n+1}$行：每行两个整数表示一种币值的硬币．第一个整数${V(I≤}$${y≤}$${10^8)，}$表示币值．

第二个整数${B(1≤}$${B≤}$${10^6)，}$表示约翰拥有的这种硬币的个数．

输出格式

一个整数，表示约翰付给贝茜津贴得最多的周数．

样例

输入样例

3  6
10  1
1  1 00
5  1 20

输出样例

111

提示

样例说明

约翰想要每周付给贝茜${6}$美分．他有${1}$个${10}$美分的硬币、${100}$个${1}$美分的硬币、${120}$个${5}$美分的硬币．

约翰可以第一 周付给贝茜一个${10}$美分的硬币，接着的${10}$周每周付给贝茜${2}$个${5}$芙分硬币，接下来的${100}$周每周付给贝茜一个${1}$美分的硬币和${1}$个${5}$美分的硬币．共计${111}$周．