新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:65536KB
問題 
牛乳生産の記録により賞をもらったBessieに毎週の手当てを与えようとJohnは決めた。N(1<=N<=20)種類の額の硬貨を持っていて、すべての硬貨は次に大きい額の硬貨の額を割り切る。(たとえば、1セント、5セント、10セント、50セント、のように。)この硬貨を利用して、Bessieに毎週少なくともC(1<=C<=1,000,000)だけ支払いをしたい。Johnが最大何週間Bessieに支払えるか求めるのを助けてほしい。
入力
1行目はスペース区切りの2つの整数N,C。
2行目からN+1行目はそれぞれ硬貨に相当するスペース区切りの2つの整数。硬貨の価値V(1<=V<=1,000,000)とその効果をJohnが持っている枚数B(1<=B<=1,000,000)である。
出力
JohnがBessieに少なくともCだけの額を支払うことのできる週の数。
入力の例
3 6 10 1 1 100 5 120
出力の例
111
ヒント
入力:JohnはBessieに毎週6セント支払いたい。1セント硬貨を100枚、5セント硬貨を120枚、10セント硬貨を1枚持っている。
出力:JohnはBessieに10セントコイン1枚を1週間、5セントコイン2枚を10週間、1セントコイン1枚と5セントコイン1枚を100週間支払うことができる。
出典
USACO 2005 October Silver
