Профессор Дамблдор помогает Гарри уничтожать крестражи. Он отправился в Дом Мраксов, так как догадывался, что там может находиться крестраж. Профессор заметил кольцо Марвала Мракса и определил, что это крестраж. Несмотря на то, что профессор Дамблдор уничтожил его, он оказался проклят. Профессор Снегг помогает Дамблдору снять проклятие. Для этого он собирается дать Дамблдору ровно x капель зелья, которое он приготовил.
Значение x вычисляется как максимум p·ai + q·aj + r·ak для данных p, q, r и массива a1, a2, ... an при условии, что 1 ≤ i ≤ j ≤ k ≤ n. Помогите Снеггу определить x. Учтите, что x может быть отрицательным, в таком случае Снегг не сможет спасти Дамблдора.
Выходные данные
Выведите максимальное значение выражения p·ai + q·aj + r·ak с учётом 1 ≤ i ≤ j ≤ k ≤ n.
Примечание
В первом примере можно выбрать i = j = k = 5, получив ответ 1·5 + 2·5 + 3·5 = 30.
Во втором примере можно выбрать i = j = 1, k = 5, получив ответ 12.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 1 2 3
1 2 3 4 5
|
30
|
|
2
|
5 1 2 -3
-1 -2 -3 -4 -5
|
12
|