OI题库

【题目描述】

作為創造產奶紀錄的回報，Farmer John決定開始每個星期給Bessie一點零花錢。

FJ有一些硬幣，一共有N (1 <= N <= 20)種不同的面額。每一個面額都能整除所有比它大
的面額。

他想用給定的硬幣的集合，每個星期至少給Bessie某個零花錢的數目C (1 <= C <= 
100000000)。請幫他計算他最多能支付多少個星期的零花錢。

題目名稱: allow

【输入格式】

輸入格式:

* 第一行: 兩個由空格隔開的整數: N 和 C

* 第2到第N+1行: 每一行有兩個整數表示一個面額的硬幣：硬幣面額V (1 <= V <= 
 100,000,000)和Farmer John擁有的該面額的硬幣數B (1 <= B <=
        1,000,000).

【输出格式】

* 第一行: 一個單獨的整數，表示Farmer John最多能給Bessie支付多少個星期至少為C的
 零用錢。

【样例输入】

3 6
10 1
1 100
5 120

【样例输出】

111

【提示】

輸入細節:

FJ想要每個星期給Bessie六美分。他有100個1美分硬幣，120個5美分硬幣，和一個10美分
硬幣。

【来源】

USACO Contest 2009 October Gold

http://www.cnblogs.com/waterfalleagle/articles/1589190.html