Задача H. Опять лифт

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

Условие

Высокое здание, состоящее из N этажей, оснащено только одним лифтом. Парковка находится ниже фундамента здания, что соответствует одному этажу ниже первого. Этажи пронумерованы от 1 до N снизу вверх. Про каждый этаж известно количество человек, желающих спуститься на лифте на парковку. Пусть для i-го этажа эта величина равна Ai. Известно, что лифт не может перевозить более C человек единовременно, а также то, что на преодоление расстояния в один этаж (не важно вверх или вниз) ему требуется P секунд. Какое наибольшее количество человек лифт может перевезти на парковку за T секунд, если изначально он находится на уровне парковки?

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

В первой строке входного файла содержатся целые числа N, C, P, T (1 ≤ N ≤ 100, 1 ≤ C ≤ 109, 1 ≤ P ≤ 109, 1 ≤ T ≤ 109). Вторая строка содержит последовательность N целых чисел A1, A2, …, AN (0 ≤ Ai ≤ 109). Сумма всех значений последовательности не превосходит 109.

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

Выведите наибольшее количество человек, которое лифт успеет перевезти на парковку.

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

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

0.054s 0.009s 13