BitTorrent
BitTorrent — це протокол для передачі великих файлів у одноранговій мережі, де вузли виконують роль як клієнтів, так і серверів. Це відрізняється від централізованої архітектури клієнт-сервер, де клієнти запитують ресурси у центральних серверів. Протокол дозволяє користувачам створювати групу хостів для одночасного завантаження та вивантаження файлів один від одного. Весь пакет файлів (так званий торрент) розділяється на частини, як показано на рисунку. Наприклад, пакет розміром 10 МБ може бути розділений на десять частин по 1 МБ або на сорок частин по 256 КБ. Коли хост (або пір) отримує нову частину торрента, він стає джерелом цієї частини для інших хостів, які бажають її отримати. Частини зазвичай завантажуються не послідовно, але впорядковуються в правильному порядку хостами. Кожен хост самостійно вирішує, які частини потрібно завантажити. Частини мають однаковий розмір протягом всього завантаження торрента, за винятком останньої частини, яка може бути меншою.
Ви хочете завантажити пакет файлів, але наближаєтеся до свого місячного ліміту використання Інтернету і не хочете чекати до наступного місяця. Ви прагнете завантажити максимальну кількість файлів з залишковою пропускною здатністю. Які частини потрібно завантажити?
Пакет файлів (торрент)
Вхідні дані
Вхід містить декілька тестових випадків. Кожен тестовий випадок починається з трьох цілих чисел, розділених пробілами: N, P та L, де N — це кількість файлів у торренті (1 ≤ N ≤ 3000), P — це розмір частин у КБ (1 ≤ P ≤ 1000), а L — це залишкові кілобайти від вашого місячного ліміту використання Інтернету (1 ≤ L ≤ 10^6). Друга строка тестового випадку містить N цілих додатних чисел, розділених пробілами, які не перевищують 100000, де i-те число — це розмір (у КБ) i-го файлу в торренті. Вхід завершується "0 0 0", яке не слід обробляти.
Вихідні дані
Для кожного тестового випадку виведіть рядок, що містить максимальну кількість файлів, які можна завантажити з торрента.