Vaska Abroad#2240
Vasya, a third-year student (his many friends simply call him Vaska), found himself on his first tourist trip abroad—in a truly exotic country where palm trees reach the sky, flowers shine in every color of the rainbow, and money consists only of metal coins. The coins are called "centiks". These coins are so attractive that tourists like to take them home as souvenirs. Vasya also planned to bring back a few kilograms of centiks, but at the very last moment he realized that he also needs to buy a gift for his grandmother, whose birthday is coming soon.
Now, Vasya is faced with a tough problem: he needs to buy a gift, but he also wants to take home as many centiks as possible. He counted his money, chose a gift, and now is trying to solve this problem:
He has several coins, each with a known denomination.
The gift has a known price, and Vasya must pay exactly this amount, without receiving any change.
Vasya wants to use as few coins as possible, so he can bring more coins back home.
Can you solve this problem?
The first line contains the number of coins (1 \leq n \leq 40) in Vasya's pocket. The second line contains the price of the gift for Vasya's grandmother. The third line contains integers—the denomination of each coin in Vasya's pocket. In this country, no coin denomination exceeds .
Output the minimum number of coins Vasya needs to use to pay for the gift. If there is no solution, output 0.
Example 1
Example 2