LKP '18 Contest 1 P1 - World Trade Foundation - Olympiads Online Judge

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 \leq i \leq 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 \leq N \leq 10$
$1 \le a_i \le 10^9$ $1 \leq a_{i} \leq 10^{9}$
$1 \le K \le 10^9$ $1 \leq K \leq 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

Copy

3 10
1 2 4

Sample Output 1

Copy

Sample Input 2

Copy

5 263
1 5 10 50 100

Sample Output 2

Copy

Sample Input 3

Copy

3 7
2 6 12

Sample Output 3

Copy

-1

Comments

6

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

World Trade Foundation = WTF ?????