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 100000000$, 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 100000000$, 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$.

-----Examples-----
Sample Input:
13
3 2 1 1
Sample Output:
5

Source: kattis | Difficulty: HARD
Tags: Complete search


Solutions: