Problem B
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 |
