袋子游戏

题目描述

$N$ 个袋子排成一行。第 $i$ 个袋子里装着 $x_i$ 日元(日本的货币单位)。

高桥和青木(两人都有足够的钱)轮流执行以下操作:

选择以下三种操作之一并执行:

1. 选择最左边或最右边的袋子并拿走它。
2. 付给 Snuke $A$ 日元。然后,重复以下操作 $\min(B,n)$ 次(其中 $n$ 是剩余袋子的数量):选择最左边或最右边的袋子并拿走它。
3. 付给 Snuke $C$ 日元。然后,重复以下操作 $\min(D,n)$ 次(其中 $n$ 是剩余袋子的数量):选择最左边或最右边的袋子并拿走它。

当所有袋子都被拿走时,高桥的收益定义为"(高桥拿走的袋子里的钱的总金额)−(高桥付给 Snuke 的钱的总金额)",设这个金额为 $X$ 日元。类似地,定义青木的收益为 $Y$ 日元。

当高桥和青木采取最优策略、分别最大化/最小化 $X-Y$ 时,求 $X-Y$。

输入格式

输入按以下格式从标准输入给出:

N A B C D
x_1 x_2 … x_N

输出格式

输出答案。

样例

5 10 2 1000000000 1
1 100 1 1 1

90

如果高桥和青木都采取最优策略,最终会是 $X=92$,$Y=2$。

10 45 3 55 4
5 10 15 20 25 30 35 40 45 50

85

15 796265 10 165794055 1
18804175 185937909 1934689 18341 68370722 1653 1 2514380 31381214 905 754483 11 5877098 232 31600

302361955

数据范围

• $1 \le N \le 3000$
• $1 \le x_i \le 10^9$
• $1 \le A,C \le 10^9$
• $1 \le B,D \le N$
• 输入中的所有值均为整数。