Minimum Coin Count

Interview

Time limit1sMemory limit128 MB

Summary

Given n coin denominations, compute the minimum number of coins (unlimited supply) that sum to exactly k, or -1 if impossible.

Level: Easy3 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

You are given n types of coins. Each coin type may be used any number of times.

Using these coins, make a total value of exactly k. Find the minimum number of coins needed.

Input

The first line contains n and k. (1 <= n <= 100, 1 <= k <= 10,000)

Each of the next n lines contains one coin value. Every coin value is a positive integer no greater than 100,000. The same value may appear more than once.

Output

Print the minimum number of coins needed to make total value k. If it is impossible, print -1.

Examples1

Example 1
Input
```
3 15
1
5
12
```
Expected output
```
3
```