Score : 400 points
You start with the number 0 and you want to reach the number N.
You can change the number, paying a certain amount of coins, with the following operations:
You can perform these operations in arbitrary order and an arbitrary number of times.
What is the minimum number of coins you need to reach N?
You have to solve T testcases.
The input is given from Standard Input. The first line of the input is
T
Then, T lines follow describing the T testcases. Each of the T lines has the format
N A B C D
For each testcase, print the answer on Standard Output followed by a newline.
5 11 1 2 4 8 11 1 2 2 8 32 10 8 5 4 29384293847243 454353412 332423423 934923490 1 900000000000000000 332423423 454353412 934923490 987654321
20 19 26 3821859835 23441258666
For the first testcase, a sequence of moves that achieves the minimum cost of 20 is:
For the second testcase, a sequence of moves that achieves the minimum cost of 19 is: