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

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

Условие

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

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

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

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

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

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

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

Ограничения

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

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

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

0.078s 0.010s 13