Josephine the money changer was working at her kiosk one day when she realized how irritating
it was when she had to give about 20 coins to her customer. Suddenly, she had an idea.
If she could write a program to instantly tell her how many coins she needs to make the
value, then she could just refuse to serve her customers if they choose a value that
requires her to select too many coins.
Unfortunately, Josephine, being a lazy person, doesn’t want to learn programming all
by herself. Your task is to write the program for her.
Given n (1 ≤ n ≤ 100) coins where and each coin has a value
n(i) (1 ≤ n(i) &le 10,000), and a value v (1 ≤ v &le 10,000) which is also an
integer, calculate the minimum number of coins needed to make v with the n coins provided.
POINTS: 100
PROBLEM NAME: moneychanger
INPUT FORMAT:
Line 1: The first line contains two integers, n and v, separated by a space;
Line 2...n: Each line contains one integer each, with the (i + 1)th line
representing the value of coin n(i).
INPUT DETAILS:
Every coin has a unique value. The values of the coins might not necessarily be
less than the value v.
SAMPLE INPUT:
6 99
1
2
5
10
25
50
OUTPUT FORMAT:
Line 1: A single integer which is the minimum number of coins needed to make the value v.
If it is impossible to make the value with the set of coins given, output -1.
SAMPLE OUTPUT:
6
OUTPUT DETAILS:
6 coins are needed to make 99: 50, 25, 10, 10, 2, 2