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 Ai (1 ≤ Ai ≤ 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.
The first line of input will be two space-separated integers, n and v. The following n lines of input will contain one integer each, representing Ai, the value of the ith coin.
Print the 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, print -1.
6 99 1 2 5 10 25 50
6 coins are needed to make 99: 50, 25, 10, 10, 2, 2