LKP '18 Contest 1 P1 - World Trade Foundation

View as PDF

Submit solution

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

Problem type

The World Trade Foundation has N denominations of coins, a_1, a_2, \dots, 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.


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 1

3 10
1 2 4

Sample Output 1


Sample Input 2

5 263
1 5 10 50 100

Sample Output 2


Sample Input 3

3 7
2 6 12

Sample Output 3



  • 4
    IanHu  commented on Dec. 17, 2018, 2:10 a.m.

    World Trade Foundation = WTF ?????