Висока будівля з \(N\) поверхів має лише один ліфт. Парковка знаходиться нижче фундамента будівлі (0 поверх). Поверхи пронумеровані від 1 до \(N\) знизу вгору. Про кожен поверх відомо скільки людей бажають спуститись ліфтом на парковку. Відомо, що ліфт не може перевозити більше ніж \(C\) людей одночасно, а також, що на подолання відстані в один поверх (неважливо чи вгору чи вниз) йому потрібно \(P\) секунд.

Яку найбільшу кілкьість людей може перевезти ліфт на парковку за \(T\) секунд, якщо спочатку він знаходиться на рівні парковки?

Формат вхідних даних

В першому рядку містяться чотири цілих числа \(N,C,P,T\) (\(1 \le N \le 100, 1 \le C \le 10^9, 1 \le P \le 10^9, 1 \le T \le 10^9\))
Другий рядок містить \(N\) цілих чисел - кількість людей на кожнмоу з поверхів починаючи з першого. (Сумарна кількість усіх людей не перевищує 10^9)

Формат вихідних даних

Виведіть найбільшу кількість людей, яку ліфт встигне перевезти на парковку.

Приклад вхідних даних-1

4 5 2 15
0 1 2 3

Приклад вихідних даних-1

3

Приклад вхідних даних-2

4 5 2 18
0 1 2 3

Приклад вихідних даних-2

5

Приклад вхідних даних-2

3 2 1 9
1 1 1

Приклад вихідних даних-2

3