SPOJ in Gyumri

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

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

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

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

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

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

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

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

Примеры