A22530.游戏

提高+/省选-

省选

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

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

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

输入格式

输入有两行。

第一行有 4 个整数 nnkkaabb,分别满足 1kn2501 \le k \le n \le 2500ab750000 \le a \le b \le 75000

第二行有 nn 个整数,依次为 x1x_1xnx_n,给出了每一张卡片上的数字。

每一张卡片上的数字 xix_i 都满足 0xi3000\le x_i \le 300

输出格式

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

输入输出样例

  • 输入#1

    4 2 58 100
    10 10 50 80

    输出#1

    15
  • 输入#2

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

    输出#2

    1782

说明/提示

1kn201\le k\le n\le 200ab60000\le a\le b\le 6000

首页