Loading [MathJax]/jax/output/CommonHTML/jax.js

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

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

Условие

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

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

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

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

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

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

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

0.064s 0.008s 13