Васька за кордоном#2240

Васька за кордоном

1 секунда

256 мегабайтів

Дуже легка

Вася, студент третього курсу (його друзі просто називають його Ваською), вперше потрапив у туристичну поїздку за кордон — у дуже екзотичну країну, де пальми сягають неба, квіти сяють всіма барвами веселки, а гроші — лише металеві монети. Монети називаються "центиками". Ці монети настільки привабливі, що туристи люблять брати їх додому як сувеніри. Вася також збирався привезти кілька кілограмів центиків, але в останній момент згадав, що йому потрібно купити подарунок для бабусі, у якої скоро день народження.

Тепер перед Васею стоїть складна задача: йому потрібно купити подарунок, але також хочеться забрати додому якомога більше центиків. Він перерахував гроші, вибрав подарунок і тепер намагається розв'язати таку задачу:

У нього є кілька монет, кожна з відомим номіналом.
Ціна подарунка відома, і Вася повинен сплатити рівно цю суму без решти.
Вася хоче використати якомога менше монет, щоб більше залишити собі.

Чи зможете ви розв'язати цю задачу?

Вхідні дані

У першому рядку записане число монет $n$ ( $1 \leq n \leq 40$ 1 \leq n \leq 40) у кишені Васі. У другому рядку вказана ціна подарунка $p$ для бабусі Васі. У третьому рядку — $n$ цілих чисел — номінали кожної монети у кишені Васі. Відомо, що в цій країні номінал монет не перевищує $250$ .

Вихідні дані

Виведіть мінімальну кількість монет, які Вася повинен віддати за подарунок. Якщо розв'язку немає, виведіть 0.

Приклади

Приклад 1

Приклад 2