ТШ 2022 - Sandcraft (45 баллов)

Задача B. Sandcraft (45 баллов) ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	А. Кленин	Ограничение времени:	2 сек
Входной файл:	input.txt	Ограничение памяти:	8 Мб
Выходной файл:	output.txt

Условие

Имеется N песчаных карьеров, песок с которых доставляют на склад при помощи K одинаковых грузовиков. Грузовики движутся с постоянной скоростью, которая позволяет им преодолеть расстояние до i-го карьера за d_i часов.

Для того, чтобы заполнить грузовик песком, требуется ровно W часов. Одновременно на одном карьере может загружаться только один грузовик. Разгрузка любого колиества грузовиков на складе происходит моментально.

Требуется определить максимальный объём песка (измеренный в грузовиках), который можно доставить на склад за T часов.

Формат входного файла

Входной файл содержит числа N K W T, за которыми следует N чисел d₁ d₂ … d_N. Все числа — целые.

Формат выходного файла

Выходной файл должен содержать единственное целое число (возможно, ноль) — максимальный объём песка.

Ограничения

1 ≤ N,K,W,d_i ≤ 100, 1 ≤ T ≤ 1000.

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`2 2 1 8 3 5`	`2`
2	`2 2 3 15 5 6`	`2`