Takahashi（先手）和 Aoki（后手）在玩游戏。他们有无限的钱，从左到右一共有 $N$ 个物品，第 $i$ 个价值 $x_i$，两个人轮流操作，每次轮到的一个人可以做 $3$ 种操作之一（假设还剩下 $n$ 个物品）。

• 拿走最左边或者最右边的物品。
• 付给 Snuke $A$ 块钱，然后重复以下操作 $\min(B,n)$ 次：拿走最左边或者最右边的物品。
• 付给 Snuke $C$ 块钱，然后重复以下操作 $\min(D,n)$ 次：拿走最左边或者最右边的物品。

定义一个人的最大收益是拿到的所有东西的价值之和减去付给 Snuke 的钱数。

请问如果 $2$ 个人都使用最优策略，使得自身的收益减去对方的收益尽量的大，那么最终 Takahashi 的收益减去 Aoki 的收益会是多少？

• $1\le B,D\le N\le 3000,A,C\le 10^9$