题目描述

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

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

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

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

输入格式

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

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

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

输出格式

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

样例

输入样例

3  6
10  1
1  1 00
5  1 20

输出样例

111

提示

样例说明

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

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