Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0233 - БЕЗ СДАЧИ

   Все периодически сталкиваются с ситуацией, когда у кассира нет сдачи и приходится искать по карманам мелочь, чтобы набрать в точности нужную сумму. Чтобы избежать тех случаев, когда несмотря на все усилия, собрать требуемую сумму так и не удается, можно всегда иметь при себе такой набор денежных знаков разного номинала, чтобы из него точно можно было набрать любую сумму (разумеется, до какого-то разумного предела). При этом, конечно, желательно, чтобы общее количество денежных знаков было минимально возможным.

   Зная все возможные номиналы, Вам нужно определить, какое минимальное количество денеж- ных знаков необходимо для того, чтобы набрать из них любую сумму от 1 до некоторого заданного числа включительно.

Формат входных данных

   В первой строке одно целое положительное число N – количество возможных номиналов денеж- ных единиц, 1 N 1 000.

   Во второй строке N различных целых положительных чисел через пробел – возможные номи- налы. Каждое из чисел не превышает 106. Гарантируется, что одно из этих чисел – 1.

   В третьей строке одно целое положительное число S, 1 S 1010.

Формат выходных данных

   В первой и единственной строке одно целое положительное число – минимальное количество денежных знаков доступных номиналов, достаточное для того, чтобы набрать любую сумму от 1 до S включительно.

Примеры

stdin

stdout

1

4
1 3 4 7
7

4


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-10-08
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.West Siberian QF 2014.D

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.