LKP '18 Contest 1 P1 - World Trade Foundation

View as PDF

Submit solution

All submissions

Best submissions

Points: 3 (partial)

Time limit: 1.0s

Memory limit: 16M

Author:

KevinWan

Problem type

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

Constraints

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

Input Specification

On the first line, there are two space-separated integers, $N$ ~N~ $K$ ~K~.
The next line contains $N$ ~N~ space-separated integers, $a_i$ ~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$ ~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

-1

Comments

6

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

World Trade Foundation = WTF ?????