/ Vijos / 题库 /

游戏

游戏

描述

小雪与小可可正在玩一种数字游戏。他们准备了n卡片,每一张卡片上都有一个整数。游戏开始后,小雪会先选择一个不小于a且不大于b的整数t,并告诉小可可这个数字t是多少。之后小可可会挑出恰好k张卡片,并将这k张卡片上的数字相加,得到的和数记为m。

小雪希望t和m差的绝对值尽可能大,而小可可却希望t和m差的绝对值尽可能小。在游戏开始前,他们二人都知道n,a,b和k是多少,也知道每一张卡片上的数字是多少。在小雪决定了t的大小后,不能再修改,之后才由小可可挑选纸牌。

小雪希望知道,在二人都尝试最优策略的情况下,t和m差的绝对值最大可以有多大?

格式

输入格式

输入有两行。

第一行有4个整数n,k,a和b,分别满足1<=k<=n<=250且0<=a<=b<=75000。

第二行有n个整数,依次为x[1]到x[n],给出了每一张卡片上的数字。

每一张卡片上的数字x[i]都满足0<=x[i]<=300。

输出格式

输出一行,只有一个整数,表示t和m差的绝对值最大可以有多大。

样例1

样例输入1

4 2 58 100
10 10 50 80

样例输出1

15

样例2

样例输入2

8 3 1300 1800
2 0 1 9 1 4 0 5

样例输出2

1782

限制

对于30%的数据,1<=k<=n<=20且0<=a<=b<=6000。

对于80%的数据,1<=k<=n<=65且0<=a<=b<=19500。

对于100%的数据,1<=k<=n<=250且0<=a<=b<=75000。

信息

ID
1987
难度
8
分类
(无)
标签
(无)
递交数
334
已通过
50
通过率
15%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

春夏之交邀请赛