Problem A. BitTorrent
Input file name: bittorrent.in
Output file name: bittorrent.out
Time limit: 2 s
Memory limit: 256 MB

BitTorrent — пиринговый (peer-to-peer) сетевой протокол для передачи больших файлов, в котором узлы действуют и как клиенты и как серверы, в отличие от централизованной клиент-серверной архитектуры, где клиентские узлы запрашивают ресурсы у центрального сервера. Действительно, протокол BitTorrent позволяет группе хостов одновременно раздавать и получать друг у друга файлы, что снижает нагрузку и зависимость от каждого клиента-источника и обеспечивает избыточность данных.

А именно, раздача (так называемый торрент) включает в себя набор файлов, разбитых на фрагменты, как показано на рисунке. Например, пакет файлов общим размером в 10 МиБ может быть разделён на десять фрагментов размера 1 MиБ или на сорок фрагментов по 256 КиБ. Как только хост (так называемый пир) получает новый фрагмент торрента, он становится источником этого фрагмента для других хостов, которым также необходим этот фрагмент. Как правило, фрагменты загружаются непоследовательно и переставляются в правильном порядке самими пирами. Каждый хост самостоятельно управляет тем, какие фрагменты должны быть загружены. Фрагменты имеют одинаковый размер в рамках одного торрента, за исключением последнего, который может иметь меньший размер. Фрагменты скачиваются и закачиваются только целиком.

Вы хотите скачать один торрент, но приближается ваш месячный лимит входящего интернет-трафика, и на скачивание всех файлов остатка может не хватить. Тем не менее, вы не желаете ждать до следующего месяца и хотите заполучить хотя бы некоторые файлы из торрента. Какое наибольшее число отдельных файлов можно скачать, уложившись в лимит?

Input

В первой строке через пробел записано три целых числа N, P и L, где N — количество файлов в торренте (1 ≤ N ≤ 3000), P — размер фрагмента в КиБ (1 ≤ P ≤ 1000), L — месячный остаток интернет-трафика в КиБ (1 ≤ L ≤ 1 000 000). Во второй строке через пробел записано N чисел S1, S2, …, SN, где Si — размер i-го файла в КиБ (1 ≤ Si ≤ 100 000). Файлы перечислены в порядке следования в торренте.

Output

Выведите одно число — максимальное количество файлов, которые можно скачать.

Examples

bittorrent.in bittorrent.out
3 3 13
5 5 7
2
7 2 16
6 11 3 3 8 1 8
4

Note

Вместо десятичных приставок кило-, мега- и т. д., обозначающих 103, 106 и т. д. единиц, международная электротехническая комиссия в марте 1999 года предложила использовать двоичные приставки кеби-, меби- и т. д., обозначающие 210, 220 и т. д. едиинц.