分数: 550 点
问题陈述
N 袋子排列成一排。 的 i第袋包含 x_i 日元(日本货币)。
拥有足够金钱的高桥和青木轮流执行以下动作:
- 选择以下三个操作之一并执行。
- 选择最左边或最右边的袋子并拿走它。
- 支付 A 日元到 Snuke。 然后,重复以下动作 \min(B,n) 次(其中 n 是剩余袋子的数量):选择最左边或最右边的袋子并拿走。
- 支付 C 日元到 Snuke。 然后,重复以下动作 \min(D,n) 次(其中 n 是剩余袋子的数量):选择最左边或最右边的袋子并拿走。
当所有袋子被拿走时,高桥的收益定义为“(高桥拿走的袋子中的总金额)-(高桥支付给snuke的总金额)”;令这个金额为 X 日元。 我们类似地定义 Aoki 的收益,用下式表示金额: Y 日元。
查找 X-Y 如果高桥和青木分别做出最大化和最小化的最佳动作 X-Y.
约束
- 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
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A B C D x_1 x_2 \ldots x_N
输出
打印答案。
示例输入 1
5 10 2 1000000000 1 1 100 1 1 1
示例输出 1
90
如果高桥和青木做出最佳动作,最终会是 X=92 和 Y=2.
示例输入 2
10 45 3 55 4 5 10 15 20 25 30 35 40 45 50
示例输出 2
85
示例输入 3
15 796265 10 165794055 1 18804175 185937909 1934689 18341 68370722 1653 1 2514380 31381214 905 754483 11 5877098 232 31600
示例输出 3
302361955