World Trade Foundation

View as PDF

Submit solution

Points: 3 (partial)
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type

The World Trade Foundation has N denominations of coins, a_1, a_2, \ldots , a_N where a_i is a multiple of a_{i-1} for 2\le i\le N. The WTF wishes to perform a transaction that costs exactly K Quunar (the local currency). Because they value efficiency over all else, determine the minimum number of coins they need to get exactly K Quunar, or print -1 if this is not possible.

Constraints

1 \le N \le 10
1 \le a_i \le 10^9
1 \le K \le 10^9
It is guaranteed that a_i is a multiple of a_{i-1}.

Input Specification

On the first line, there are two space-separated integers, N K.
The next line contains N space-separated integers, a_i, the values of the coins (in Quunar).

Output Specification

On one line, output the minimum number of coins needed to make a sum of exactly K Quunar or print -1 if this is not possible.

Sample Input

3 10
1 2 4

Sample Output

3

Sample Input 2

5 263
1 5 10 50 100

Sample Output 2

7

Sample Input 3

3 7
2 6 12

Sample Output 3

-1

Comments


  • 2
    IanHu  commented on Dec. 16, 2018, 9:10 p.m.

    World Trade Foundation = WTF ?????