B. Кольцо Марвала Мракса
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Профессор Дамблдор помогает Гарри уничтожать крестражи. Он отправился в Дом Мраксов, так как догадывался, что там может находиться крестраж. Профессор заметил кольцо Марвала Мракса и определил, что это крестраж. Несмотря на то, что профессор Дамблдор уничтожил его, он оказался проклят. Профессор Снегг помогает Дамблдору снять проклятие. Для этого он собирается дать Дамблдору ровно x капель зелья, которое он приготовил.

Значение x вычисляется как максимум p·ai + q·aj + r·ak для данных p, q, r и массива a1, a2, ... an при условии, что 1 ≤ i ≤ j ≤ k ≤ n. Помогите Снеггу определить x. Учтите, что x может быть отрицательным, в таком случае Снегг не сможет спасти Дамблдора.

Входные данные

В первой строке находятся 4 целых числа n, p, q, r ( - 109 ≤ p, q, r ≤ 109, 1 ≤ n ≤ 105).

Во второй строке заданы n целых чисел a1, a2, ... an ( - 109 ≤ ai ≤ 109), разделённых пробелами.

Выходные данные

Выведите максимальное значение выражения p·ai + q·aj + r·ak с учётом 1 ≤ i ≤ j ≤ k ≤ n.

Примеры
Входные данные
5 1 2 3
1 2 3 4 5
Выходные данные
30
Входные данные
5 1 2 -3
-1 -2 -3 -4 -5
Выходные данные
12
Примечание

В первом примере можно выбрать i = j = k = 5, получив ответ 1·5 + 2·5 + 3·5 = 30.

Во втором примере можно выбрать i = j = 1, k = 5, получив ответ 12.