Fewest Notes and Coins

Easy#greedy· solved by 0 · time limit 2.0 s

Indian currency comes in 1, 2, 5, 10, 20, 50, 100, 200, 500 and 2000. Find the minimum number of notes/coins that add up to $x$ rupees. (For these denominations, greedily taking the largest note that fits is optimal.)

Input

A line with 10 (the number of denominations), the line 1 2 5 10 20 50 100 200 500 2000, and then $x$ .

Output

The minimum count.

Constraints

$1 \le x \le 10^9$

Sample 1

Input

10
1 2 5 10 20 50 100 200 500 2000
93

Output