[USACO09OCT] Allowance G
题目描述
作为创造产奶纪录的回报,Farmer John 决定开始每个星期给Bessie 一点零花钱。
FJ 有一些硬币,一共有 $N (1 \le N \le 20)$ 种不同的面额。每一个面额都能整除所有比它大的面额。
他想用给定的硬币的集合,每个星期至少给 Bessie 某个零花钱的数目 $C (1 \le C \le 100000000)$。请帮他计算他最多能支付多少个星期的零花钱。
输入输出格式
输入格式
第 $1$ 行: 两个由空格隔开的整数: $N$ 和 $C$;
第 $2$ 到第 $N+1$ 行: 每一行有两个整数表示一个面额的硬币:硬币面额 $V (1 \le V \le 100,000,000)$ 拥有的该面额的硬币数 $B (1 \le B \le 1,000,000)$。
输出格式
第 $1$ 行: 一个单独的整数,表示最多能给支付多少个星期至少为 $C$ 的零用钱。
输入输出样例
输入样例 #1
3 6
10 1
1 100
5 120
输出样例 #1
111