Задача №3380. Лифт
формула, моделирование, комбинаторика, динамика, бинпоиск, сортировка структур.
Высокое здание, состоящее из \(N\) этажей, оснащено только одним лифтом. Парковка находится ниже фундамента здания, что соответствует одному этажу ниже первого. Этажи пронумерованы от \(1\) до \(N\) снизу вверх. Про каждый этаж известно количество человек, желающих спуститься на лифте на парковку. Пусть для i-го этажа эта величина равна \(A_i\). Известно, что лифт не может перевозить более \(C\) человек единовременно, а также то, что на преодоление расстояния в один этаж (не важно вверх или вниз) ему требуется \(P\) секунд. Какое наибольшее количество человек лифт может перевезти на парковку за \(T\) секунд, если изначально он находится на уровне парковки?
В первой строке входного файла содержатся целые числа \(N\), \(C\), \(P\), \(T\) (\(1 \leq N \leq 100\), \(1 \leq C \leq 10^9\), \(1 \leq P \leq 10^9\), \(1 \leq T \leq 10^9\)). Вторая строка содержит последовательность \(N\) целых чисел \(A_1\), \(A_2\), ..., \(A_N\) (\(0 \leq A_i \leq 10^9\)). Сумма всех значений последовательности не превосходит \(10^9\).
Выведите наибольшее количество человек, которое лифт успеет перевезти на парковку.
4 5 2 15 0 1 2 3
3
4 5 2 18 0 1 2 3
5
3 2 1 9 1 1 1
3