[ABC303G] Bags Game

题目描述

有一个长度为N的背包序列，第i个背包里面有x[i]块钱。 两个人玩游戏，起初两个人都有充足的钱，每一轮可以做如下三种选择之一： （1）从左边或者右边拿走一个背包。 （2）花A块钱贿赂裁判，然后执行操作（1）B次，如果不够B个包，就拿完。 （3）花C块钱贿赂裁判，然后执行操作（1）D次，如果不够D个包，就拿完。 定义两个人最终赚的钱分别叫X,Y。 A希望X-Y最大，B希望X-Y最小，问最终答案是多少。

输入格式

第一行$N,A,B,C,D$

第二行$N$个整数$x_i$

输出格式

输出答案咯。

样例 #1

样例输入 #1

5 10 2 1000000000 1
1 100 1 1 1

样例输出 #1

90

样例 #2

样例输入 #2

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

样例输出 #2

85

样例 #3

样例输入 #3

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

样例输出 #3

302361955

数据范围

• $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$