NOI
全国青少年信息学奥林匹克联赛(NOIPOJ)在线评测系统
NOIPOJ在线评测系统
Problem61--游戏 [game]

61: 游戏 [game]

Time Limit: 1000 Sec  Memory Limit: 128 MB
Submit: 5  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

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

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

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

Input

输入有两行。

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

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

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

Output

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

Sample Input Copy

4 2 58 100
10 10 50 80

Sample Output Copy

15

HINT

数据规模:

对于 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。

Source/Category