CF855B.Marvolo Gaunt's Ring

Professor Dumbledore is helping Harry destroy the Horcruxes. He went to Gaunt Shack as he suspected a Horcrux to be present there. He saw Marvolo Gaunt's Ring and identified it as a Horcrux. Although he destroyed it, he is still affected by its curse. Professor Snape is helping Dumbledore remove the curse. For this, he wants to give Dumbledore exactly x drops of the potion he made.

Value of x is calculated as maximum of p·a__i + q·a__j + r·a__k for given p, q, r and array _a_1, _a_2, ... a__n such that 1 ≤ i ≤ j ≤ k ≤ n. Help Snape find the value of x. Do note that the value of x may be negative.

邓布利多教授正在帮助哈利摧毁魂器。他前往冈特老宅，因为他怀疑那里藏有一个魂器。他发现了马沃罗·冈特的戒指，并确认其为魂器。尽管他已将其摧毁，但仍受到其诅咒的影响。斯内普教授正协助邓布利多解除该诅咒。为此，他需要恰好给邓布利多服用 x 滴自己配制的魔药。

x 的值定义为：对给定的 p, q, r 和数组 _a_₁, _a_₂, ..., a__n，在满足 1 ≤ i ≤ j ≤ k ≤ n 的条件下，表达式 p·a__i + q·a__j + r·a__k 的最大值。请帮助斯内普求出 x 的值。请注意，x 的值可能为负数。

First line of input contains 4 integers n, p, q, r ( - 109 ≤ p, q, r ≤ 109, 1 ≤ n ≤ 105).

Next line of input contains n space separated integers _a_1, _a_2, ... a__n ( - 109 ≤ a__i ≤ 109).

输入的第一行包含 4 个整数 $n$、$p$、$q$、$r$（其中 $-10^9 \le p, q, r \le 10^9$，$1 \le n \le 10^5$）。

输入的第二行包含 $n$ 个用空格分隔的整数 $a_1,\,a_2,\,\dots,\,a_n$（其中 $-10^9 \le a_i \le 10^9$）。

Output a single integer the maximum value of p·a__i + q·a__j + r·a__k that can be obtained provided 1 ≤ i ≤ j ≤ k ≤ n.

输出一个整数，表示在满足 $1 \le i \le j \le k \le n$ 的条件下，$p \cdot a_i + q \cdot a_j + r \cdot a_k$ 能取得的最大值。

In the first sample case, we can take i = j = k = 5, thus making the answer as 1·5 + 2·5 + 3·5 = 30.

In second sample case, selecting i = j = 1 and k = 5 gives the answer 12.

在第一个样例中，我们可以取 $i = j = k = 5$，从而得到答案为 $1 \cdot 5 + 2 \cdot 5 + 3 \cdot 5 = 30$。

在第二个样例中，选择 $i = j = 1$ 且 $k = 5$，可得答案为 $12$。