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