Задачи
Васька за границей
Васька за границей
\includegraphics{https://static.e-olymp.com/content/15/1582ca2044456e68ae755dee17decd14207dc029.jpg}
Студент третьего курса Иванов Василий (которого многочисленные друзья зовут просто Васькой) оказался в турпоездке за границей - первый раз в жизни, да еще в такой экзотической стране, где пальмы растут до неба, цветы сияют всеми цветами радуги, а деньги - только металлические монеты. Монеты называются \textit{"центиками"}. И такие эти монетки симпатичные, что все туристы увозят их в качестве сувениров. Василий тоже собирался увезти пару килограммов \textit{центиков} в качестве сувениров, но в самый последний момент сообразил, что бабушке кроме \textit{центиков} нужно бы еще купить подарок, так как у нее скоро день рождения.
Вот и возникла перед Васькой жуткая проблема - и подарок надо купить, и \textit{центиков} домой побольше увезти хочется. Деньги Васька пересчитал, подарок выбрал и теперь решает сложную задачу:
\begin{itemize}
\item есть монеты, номинал каждой известен,
\item цена подарка известна, и Васька должен заплатить за него точно требуемую сумму без сдачи,
\item Вася хочет отдать как можно меньше монет, чтобы побольше монет увезти домой.
\end{itemize}
Интересно, а Вы сможете решить эту задачу?
\InputFile
Первая строка содержит количество монет \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{40}) в кармане у Васьки. Следующая строка содержит стоимость подарка \textbf{p} для Васиной бабушки. Третья строка содержит \textbf{n }целых чисел - номинал каждой из монет в Васином кармане. Известно, что в той дивной стране номинал монет не превышает \textbf{250}.
\OutputFile
Выведите минимальное количество монет, которые Вася отдаст за подарок. Если решения нет, выведите число \textbf{0}.
Входные данные #1
10 100 10 20 30 40 55 60 65 99 101 5
Выходные данные #1
2
Входные данные #2
12 70 5 5 5 5 5 5 5 5 5 5 5 100
Выходные данные #2
0
Объяснение: В первом примере можно заплатить 40+60, а во втором - нет решения.