The popularity of the district Olympiad in Informatics is growing year by year. At the same time, the organizers must print out in advance both the conditions of the tasks and other materials of the Olympiad (questionnaires, memos, etc.). This year they estimated the volume of printed matter at N sheets.
A company that is ready to reproduce printed materials offers the following financial terms. She prints one sheet for A1 rubles, 10 sheets — for A2 rubles, 100 sheets — for A3 rubles, 1000 sheets — for A4 rubles, 10 000 sheets — for A5 rubles, 100 000 sheets — for A6 rubles and 1 000 000 sheets — for A7 rubles. However, it is not guaranteed that one sheet in a larger order will cost less than in a smaller one. And it may even turn out that it will be beneficial for any party to use the tariff for one sheet.
The printing of a specific order is made either by a combination of several tariffs, or by ordering a larger batch. For example, 980 sheets can be printed by ordering 9 batches of 100 sheets plus 8 batches of 10 sheets, 98 orders of 10 sheets, 980 orders of 1 sheet, or ordering 1000 (or even 10 000 or more) sheets if that is will be more profitable.
It is required to determine the minimum amount of money in rubles, which will be enough to fulfill the order, based on the given volume of the order in N sheets.
Input
The input to the program is first given the number N (1 ≤ N ≤ 2 × 109) — the number of sheets in the order. The next 7 input lines contain natural numbers A1, A2, A3, A4, A5, A6, A7 respectively (1 ≤ Ai ≤ 106).
Imprint
Print one number — the minimum amount of money in rubles that is needed to complete the order. It is guaranteed that the correct answer will not exceed 2 × 10
9.
Examples
| # |
Input |
Output |
| 1 |
980
1
9
90
900
1000
10000
10000
| 882 |
| 2 |
980
1
10
100
1000
900
10000
10000
| 900 |