A2051. Allowance G
编程题
普及+/提高
知识点
题目描述
作为创造产奶纪录的回报，Farmer John 决定开始每个星期给Bessie 一点零花钱。
FJ 有一些硬币，一共有 $N (1 \le N \le 20)$ 种不同的面额。每一个面额都能整除所有比它大的面额。
他想用给定的硬币的集合，每个星期至少给 Bessie 某个零花钱的数目 $C (1 \le C \le 100000000)$。请帮他计算他最多能支付多少个星期的零花钱。
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)$。
第 $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
说明/提示
第 $1$ 行: 一个单独的整数，表示最多能给支付多少个星期至少为 $C$ 的零用钱。