Hide

Problem H
Getting Rid of Coins

When Per was living in New York, he couldn’t use his debit card as often as in Sweden. He had to carry cash all the time and his wallet was getting heavy from all the coins he was carrying around. He was once in a candy store buying a few kilos of candy and he wanted to get rid of as many coins as possible but couldn’t figure out how to do it without getting any change back.

Task

You will be given a price $P$ that Per was going to pay. You will also be given the number of 1-, 5-, 10- and 25-cent coins that he had in his wallet. He didn’t have any notes. Find the maximum number of coins he could have used for paying the price $P$ without getting any change back.

Input

The first line of input contains an integer $P, 1\leq P\leq 100\, 000\, 000$, the price Per was going to pay. On the second line there are 4 space separated integers $N_1, N_5, N_{10}, N_{25}; 0\leq N_1, N_5, N_{10}, N_{25}\leq 100\, 000\, 000$, the number of 1-, 5-, 10- and 25-cent coins in Per’s wallet.

Output

If Per couldn’t pay exactly $P$ without getting any change back, output Impossible on a single line. Otherwise output the maximum number of coins Per could use to pay the price $P$.

Sample Input 1 Sample Output 1
13
3 2 1 1
5
Sample Input 2 Sample Output 2
13
2 2 1 1
Impossible

Please log in to submit a solution to this problem

Log in