AT_abc303_g [ABC303G] Bags Game

有 $N$ 个袋子从左到右排成一列，第 $i$ 个袋子里有 $x_i$ 日元。 高桥君和青木君都拥有足够多的钱，他们轮流进行操作，高桥君先手。每次操作可以选择以下三种之一： - 选择并取走最左端或最右端的一个袋子。 - 向すぬけ君支付 $A$ 日元，然后重复 $\min(B, n)$ 次“选择并取走最左端或最右端的一个袋子”的操作（$n$ 为当前剩余袋子的数量）。 - 向すぬけ君支付 $C$ 日元，然后重复 $\min(D, n)$ 次“选择并取走最左端或最右端的一个袋子”的操作（$n$ 为当前剩余袋子的数量）。 当所有袋子都被取走时，高桥君的收益定义为“高桥君取走的所有袋子中金额的总和减去高桥君支付给すぬけ君的总金额”，记为 $X$ 日元。青木君的收益同理，记为 $Y$ 日元。 请计算在两人都采取最优策略的情况下，使 $X-Y$ 最大化的 $X-Y$ 的值。

输入从标准输入读入，格式如下： > $N\ A\ B\ C\ D\ x_1\ x_2\ \ldots\ x_N$

请输出答案。

### 限制条件 - $1 \leq N \leq 3000$ - $1 \leq x_i \leq 10^9$ - $1 \leq A, C \leq 10^9$ - $1 \leq B, D \leq N$ - 输入均为整数 ### 样例解释 1 当高桥君和青木君都采取最优策略时，$X=92,\ Y=2$。 由 ChatGPT 4.1 翻译