题目描述

小雪与小可可正在玩一种数字游戏。他们准备了 $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 \le k \le n \le 250$ 且 $0 \le a \le b \le 75000$。

第二行有 $n$ 个整数，依次为 $x_1$ 到 $x_n$，给出了每一张卡片上的数字。

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

输出格式

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

4 2 58 100
10 10 50 80

15

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

1782

提示

对于 30% 的数据， $1\le k\le n\le 20$ 且 $0\le a\le b\le 6000$。

对于 80% 的数据， $1\le k\le n\le 65$ 且 $0\le a\le b\le 19650$。

对于 100% 的数据， $1\le k\le n\le 250$ 且 $0\le a\le b\le 75000$。