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) types of coins, where each type of coin has a value
n(i) (1 ≤ n(i) ≤ 10,000), and a value v (1 ≤ v ≤ 10,000) which is also an
integer, calculate the minimum number of coins needed to make v with the n coins provided.
Note that you are allowed to use the same type of coin multiple times.
PROBLEM NAME: moneychanger
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 of type i, n(i).
Every type of coin has a unique value. The values of the coins might not necessarily be
less than the value v.
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.
6 coins are needed to make 99: 50, 25, 10, 10, 2, 2