moneychanger

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.

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 of type i, n(i). 

INPUT DETAILS:

Every type of 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

Submitting to 'moneychanger'


You're not logged in! Click here to login


Submitting .cpp to 'moneychanger'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 109
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 100
2 0