← 返回题目列表

Codeforces · 855/B

B. 马沃罗·冈特的戒指

中文机器翻译题面 查看原题

邓布利多教授正在帮助哈利摧毁魂器。他去了冈特小屋,因为他怀疑那里有魂器。他看到了马沃罗·冈特的戒指,并认出它是一个魂器。虽然他摧毁了它,但他仍然受到它的诅咒的影响。斯内普教授正在帮助邓布利多解除诅咒。为此,他想给邓布利多恰好x滴他制作的魔药。

对于给定的 p、q、r 和数组 a1、a2、...an,x 的值计算为 p·ai + q·aj + r·ak 的最大值,使得 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)。

输出

输出一个整数,即在 1 ≤ i ≤ j ≤ k ≤ n 的情况下可获得的 p·ai + q·aj + r·ak 的最大值。

示例

输入 #1

5 1 2 3
1 2 3 4 5

输出 #1

30

输入 #2

5 1 2 -3
-1 -2 -3 -4 -5

输出 #2

12

注意

在第一个示例中,我们可以取 i = j = k = 5,从而使答案为 1·5 + 2·5 + 3·5 = 30。

在第二个示例中,选择 i = j = 1 且 k = 5 给出答案 12。