CSES - Minimizing Coins | Giảm thiểu đồng xu

View as PDF
All submissions
Best submissions
Time limit:
Pypy 3 1.5s
Authors:
Flower_On_Stone , kitsune
Problem type
Points: 1200 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

Consider a money system consisting of \(n\) coins. Each coin has a positive integer value. Your task is to produce a sum of money \(x\) using the available coins in such a way that the number of coins is minimal.

For example, if the coins are \(\{1,5,7\}\) and the desired sum is \(11\), an optimal solution is \(5+5+1\) which requires \(3\) coins.

Input

  • The first input line has two integers \(n\) and \(x\): the number of coins and the desired sum of money.

  • The second line has \(n\) distinct integers \(c_1,c_2,\ldots,c_n\): the value of each coin.

Output

  • Print one integer: the minimum number of coins. If it is not possible to produce the desired sum, print \(−1\).

Constraints

  • \(1 \le n \le 100\)
  • \(1 \le x \le 10^6\)
  • \(1 \le c_i \le 10^6\)

Example

Sample input

3 11
1 5 7

Sample output

3

Comments