题目描述

受到数学中的组合的启发，小码哥发明了一种好玩的组合游戏。

有编号为 $1$ 到 $n$ 的 $n$ 个数字，编号为 $i$ 的数字的值是 $a_i$，其中 $a_i$ 可正可负。

小码哥需要从这些数字里选取 $k$ 个组合，要求：

1. 每个组合的数字的个数不少于 $L$ 且不多于 $R$。
2. 选择组合的时候，要求选择编号连续的数字（不支持循环连续，即类似于编号 $n-1$，编号 $n$，编号 $1$ 不构成一个连续）。
3. 组合之间两两不相同。（两个组合相同，当且仅当两个组合选择的数字的编号完全相同，比如组合 $1$ 选择了编号为 $2、3、4$ 的数字，组合 $2$ 也选择了编号为 $2、3、4$ 的数字，则它们相同）。

对于选出 $k$ 个组合，有很多种的选法。但是小码哥想知道所有的选法里，能够让这 $k$ 个组合的所有的数字的和最大，这个最大值是多少。

输入格式

第一行包含四个正整数 $n,k,L,R$（$1 \le n,k \le 500000$ ； $1 \le L \le R \le n$ ）。其中 $n$ 为备选的数字的个数，$k$ 为需要组成的组合个数，$L$ 和 $R$ 分别是组合中含有的数字个数的下限和上限；

接下来 $n$ 行，每行包含一个整数 $a_i$（$-1000 \le a_i \le 1000$ ），表示编号为 $i$ 的数字 $a_i$。

输出格式

输出一个整数，表示能够组成 $k$ 个组合的数字之和的最大值。

3 2 1 10
2
5
9

30

解释 #1

样例 $1$ ：

$k=2$ ：

第 $1$ 种组合为 $(2,5,9)$

第 $2$ 种组合为 $(5,9)$

计算 $k$ 个组合总值

第 $1$ 组得出是 $2+5+9=16$

第 $2$ 组得出是 $5+9=14$

返回最终相加结果 $16+14=30$

5 4 2 8
3
3
4
1
1

42

解释 #2

样例 $2$ ：

$k=4$ ：

第 $1$ 种组合为 $(3,3,4,1,1)$

第 $2$ 种组合为 $(3,3,4,1)$

第 $3$ 种组合为 $(3,3,4)$

第 $4$ 种组合为 $(3,4,1)$

计算 $k$ 个组合总值

第一组得出是 $3+3+4+1+1=12$

第二组得出是 $3+3+4+1=11$

第三组得出是 $3+3+4=10$

第四组得出是 $3+4+1+1=9$

返回最终相加结果 $12+11+10+9=42$