moneychanger

Problem Statement

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.

Input

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.

Output

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.

Sample Input 1

6 99
1
2
5
10
25
50

Sample Output 1

6

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 to 'moneychanger'


You're not logged in! Click here to login


Submitting .cpp to 'moneychanger'


You're not logged in! Click here to login

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

Subtask Score
1 100
2 0