Vaska Abroad
Vasyl Ivanov, a third-year student affectionately known as Vaska, is on his first international trip to a country so exotic that palm trees reach the sky, flowers burst with every color of the rainbow, and the currency consists solely of metal coins called "centiks". These coins are so captivating that tourists often take them home as keepsakes. Vaska, too, planned to bring back a few kilograms of centiks as souvenirs. However, he suddenly remembered that he also needs to buy a gift for his grandmother, whose birthday is approaching.
Now, Vaska faces a dilemma: he needs to purchase a gift while still wanting to bring home as many centiks as possible. After counting his money and selecting a gift, he is left with a challenging problem:
He has several coins, each with a specific denomination.
The gift has a set price, and Vaska must pay the exact amount without receiving any change.
Vaska aims to use the fewest number of coins possible to maximize the number he can take home.
Can you help solve this problem?
Input
The first line contains the number of coins n (1 ≤ n ≤ 40) in Vaska's possession. The second line provides the cost p of the gift for his grandmother. The third line lists n integers, each representing the denomination of a coin in Vaska's pocket. In this unique country, no coin denomination exceeds 250.
Output
Output the minimum number of coins Vaska needs to use to pay for the gift. If it's impossible to pay the exact amount, output the number 0.