CF855B Marvolo Gaunt's Ring

邓布利多教授正在帮助哈利销毁魂器。他来到冈特小屋，因为他怀疑那里有一个魂器。他看到了马沃洛·冈特的戒指，并认出它是一个魂器。尽管他摧毁了它，但他仍然受到了诅咒的影响。斯内普教授正在帮助邓布利多解除诅咒。为此，他想要给邓布利多恰好 $x$ 滴他所制作的魔药。 $x$ 的值通过如下公式计算：给定 $p, q, r$ 和数组 $a_1, a_2, \ldots, a_n$，求 $p\cdot a_i + q\cdot a_j + r\cdot a_k$ 的最大值，其中 $1 \leq i \leq j \leq k \leq n$。请帮助斯内普找到 $x$ 的值。注意，$x$ 的值可能为负数。

输入的第一行包含 $4$ 个整数 $n, p, q, r$（$-10^9 \leq p, q, r \leq 10^9, 1 \leq n \leq 10^5$）。 下一行包含 $n$ 个空格分隔的整数 $a_1, a_2, \ldots, a_n$（$-10^9 \leq a_i \leq 10^9$）。

输出一个整数，即 $p\cdot a_i + q\cdot a_j + r\cdot a_k$ 能取得的最大值，其中 $1 \leq i \leq j \leq k \leq n$。

在第一个样例中，我们可以取 $i = j = k = 5$，此时答案为 $1 \cdot 5 + 2 \cdot 5 + 3 \cdot 5 = 30$。 在第二个样例中，选择 $i = j = 1$ 且 $k = 5$ 能得到答案 $12$。 由 ChatGPT 5 翻译