Fewest coins

Problem

A till has coins of several values, as many of each as needed. Print the fewest coins that add up to the amount, or -1 if it is impossible.

Input: Line 1: the coin values. Line 2: the amount.
Output: One integer.
Constraints: 1 ≤ number of coin values ≤ 12
1 ≤ each coin ≤ 10000
0 ≤ amount ≤ 10000

Example 1

Input

1 3 4
6

Output

3 + 3 uses two coins, while greedy would use three.

Example 2

Input

5 10
7

Output

-1

Try the problem first. Open one hint at a time.

Hint 1

dp[a] is one coin plus the best answer for a minus that coin, over every coin.

Hint 2

Use a large value such as float('inf') for amounts that are not reached.

Write your Python code, run it on the examples and submit it to hidden tests.