题目描述

有 $N$ 个袋子排成一行。第 $i$ 个袋子里面放着 $x_i$ 日元（日本的货币单位）。

Takahashi 和 Aoki 拥有足够的钱，他们轮流进行以下操作：

• 选择以下三种操作之一并执行。
  • 选择最左边或最右边的袋子并拿走它。
  • 向 Snuke 支付 $A$ 日元。然后重复以下操作 $\\min(B,n)$ 次（其中 $n$ 是剩下的袋子数量）：选择最左边或最右边的袋子并拿走它。
  • 向 Snuke 支付 $C$ 日元。然后重复以下操作 $\\min(D,n)$ 次（其中 $n$ 是剩下的袋子数量）：选择最左边或最右边的袋子并拿走它。

当所有的袋子都被拿走时，Takahashi 的受益定义为“（Takahashi 拿走的袋子中的钱的总数）-（Takahashi 支付给 Snuke 的总金额）”，记此金额为 $X$ 日元。我们类似地定义了 Aoki 的受益，并将金额表示为 $Y$ 日元。

如果 Takahashi 和 Aoki 分别采取最优策略来最大化和最小化 $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

如果 Takahashi 和 Aoki 采取最优策略，结果将是 $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