World Trade Foundation

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.


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


Sample Input 2

5 263
1 5 10 50 100

Sample Output 2


Sample Input 3

3 7
2 6 12

Sample Output 3



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

    World Trade Foundation = WTF ?????