[Usaco2005 Oct]Allowance 津贴

作为对贝茜勤恳工作的奖励，农夫约翰决定每周向她发放一笔津贴。

约翰拥有 $N$ 种不同面值的硬币。将这些面值从小到大排列后，每种硬币的面值都能整除下一种硬币的面值。例如，硬币的面值可以是 $1$ 美分、$5$ 美分、$10$ 美分和 $50$ 美分。

约翰希望每周使用现有的硬币向贝茜支付至少 $C$ 的津贴。请计算他最多能够发放多少周的津贴。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $C$，分别表示硬币种类数和每周至少需要支付的金额。

接下来 $N$ 行，每行包含两个整数 $V_i$ 和 $B_i$，分别表示一种硬币的面值以及约翰拥有的该种硬币数量。

输出格式

输出一个整数，表示约翰最多能够向贝茜发放多少周的津贴。

样例输入

3 6
10 1
1 100
5 120

样例输出

111

数据范围

• $1\le N\le 20$；
• $1\le C\le 10^8$；
• $1\le V_i\le 10^8$；
• $1\le B_i\le 10^6$；
• 将所有硬币面值从小到大排列后，每种面值都能整除下一种面值。

来源与许可

本题为 USACO 2005 October 试题「Allowance 津贴」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 6
10 1
1 100
5 120

输出

111