Marvolo Gaunt's Ring

Professor Dumbledore는 Harry가 Horcrux들을 파괴하는 것을 돕고 있다. 그는 Horcrux가 그곳에 있다고 의심하여 Gaunt Shack에 갔다. 그는 Marvolo Gaunt's Ring를 보고 그것이 Horcrux임을 알아냈다. 그것을 파괴했지만, 그는 여전히 그 저주의 영향을 받고 있다. Professor Snape는 Dumbledore가 저주를 없애는 것을 돕고 있다. 이를 위해 그는 자신이 만든 물약을 정확히 x방울 Dumbledore에게 주려고 한다.

x의 값은 주어진 p, q, r와 배열 a1, a2, ... an에 대해, 1 ≤ i ≤ j ≤ k ≤ n을 만족하는 p·ai + q·aj + r·ak의 최댓값으로 계산된다. Help Snape x의 값을 구하라. x의 값은 음수일 수도 있음에 유의하라.

입력의 첫 번째 줄에는 4개의 정수 n, p, q, r ( - 109 ≤ p, q, r ≤ 109, 1 ≤ n ≤ 105)가 주어진다.

입력의 다음 줄에는 공백으로 구분된 n개의 정수 a1, a2, ... an ( - 109 ≤ ai ≤ 109)가 주어진다.

1 ≤ i ≤ j ≤ k ≤ n을 만족할 때 얻을 수 있는 p·ai + q·aj + r·ak의 최댓값을 하나의 정수로 출력한다.

첫 번째 예제에서는 i = j = k = 5로 선택할 수 있으므로, 답은 1·5 + 2·5 + 3·5 = 30이 된다.

두 번째 예제에서는 i = j = 1이고 k = 5로 선택하면 답은 12가 된다.