All submissions for this problem are available.
As a reward for record milk production, Farmer John has decided to
start paying Mr. Robert a small weekly allowance.
FJ has a set of coins in N (1 <= N <= 20) different denominations,
where each denomination of coin evenly divides the next-larger
Using the given set of coins, he would like to pay Mr. Robert at least
some given amount of money C (1 <= C <= 100,000,000) every week.
Please help him compute the maximum number of weeks he can pay
* Line 1: Two space-separated integers: N and C
* Lines 2..N+1: Each line corresponds to a denomination of coin and
contains two integers: the value V (1 <= V <= 100,000,000) of
the denomination, and the number of coins B (1 <= B <=
1,000,000) of this denomation in Farmer John's possession.
SAMPLE INPUT :
3 6 10 1 1 100 5 120
FJ would like to pay Mr. Robert 6 cents per week. He has 100 1-cent coins,
120 5-cent coins, and 1 10-cent coin.
* Line 1: A single integer that is the number of weeks Farmer John can
pay Mr. Robert at least C allowance
FJ can overpay Mr. Robert with the one 10-cent coin for 1 week, then pay Mr. Robert
two 5-cent coins for 10 weeks and then pay Mr. Robert one 1-cent coin and one
5-cent coin for 100 weeks.
|Time Limit:||0.151515 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.