问题描述

作為創造產奶紀錄的回報，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).

樣例輸入 (文件 allow.in):

3 6
10 1
1 100
5 120

輸入細節:

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

輸出細節:

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

樣例輸出 (文件 allow.out):

111

輸出細節:

FJ可以在一個星期超額付給Bessie一個10美分硬幣。然後接下來的10個星期每星期付給Bessie兩個5美分硬幣。最後100個星期每星期付給Bessie一個1美分硬幣跟一個5美分硬幣。