[USACO09OCT] Allowance G

题目描述

有 $N$ 种不同的硬币，每种硬币有两个属性 $V_i$ 和 $B_i$ ，$V_i$ 表示硬币的面额（单位：元）， $B_i$ 表示该种硬币的硬币数量。

每种硬币的面额都能整除所有比它大的面额。

现在要用所有硬币每次支付一笔大于等于 $C$ 的费用，问最多支付多少次？

输入格式

第 $1$ 行两个整数 $N \ C(1 \le N \le 20,1 \le C \le 10^8)$。

下来 $N$ 行， 每行两个整数 $V_i \ B_i (1 \le V_i \le 10^9,1 \le B_i \le 10^6)$ 。

输出格式

一行一个整数，表示最多支付的次数。

样例输入

3 6
10 1
1 100
5 120

样例输出

111

样例解析

1个10元的硬币、100个1元的硬币、120个5元的硬币。

第一次付：一个10元硬币；

下来10次：每次付2个5元硬币；

下来100次：每次付一个1元硬币和1个5元硬币。

共计111次。