结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

展厅里沿一条直线依次排开 $n$ 块展板，从东到西编号 $1$ 到 $n$。第 $i$ 块展板的布展工作量记为 $a_i$。一块展板的布展工作不能拆开分给两个施工队，它只能整体归入某一个施工队的作业范围。

程老师要把这批展板按顺序分成恰好 $k$ 段：每一段由编号连续的一段展板组成，$k$ 段依次相接，不重不漏地盖住第 $1$ 块到第 $n$ 块。此外每段的长度有硬性限制——一段里的展板至少 $L$ 块、至多 $R$ 块。

每一段交给一个施工队独立完成，队伍之间互不调配。一个施工队的工期，在数值上就等于该段内各块展板的工作量之和。整场布展的总工期以最慢的那一段计，也就是各段工作量之和中的最大值。

为压缩总工期，程老师需要选择一种满足上述长度要求的分段方式。请计算：在所有合法分段方式中，总工期最小可能是多少。

输入格式

从文件 boards.in 中读入数据。

• 第一行四个整数 $n, k, L, R$；
• 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

输出到文件 boards.out 中。

输出一行一个整数，表示总工期的最小可能值。

样例

6 2 2 3
1 2 1 3 1 2

6

样例 1 解释

一共 $6$ 块展板要切成恰好 $2$ 段，每段长度只能是 $2$ 或 $3$，而两段长度相加必须正好等于 $6$，因此两段只能各长 $3$。切点随之唯一：只有切在第 $3$ 块之后，前一段 $[1,2,1]$ 长 $3$、后一段 $[3,1,2]$ 长 $3$；切在别的位置，总会有一段长度超出上限或不足下限。这两段的工作量之和分别为 $4$ 与 $6$，总工期取其中较大者，为 $6$。

4 1 4 4
1 2 3 4

10

样例 2 解释

只切成 $1$ 段，全部 $4$ 块展板属于同一段，该段工作量之和为 $1+2+3+4=10$，总工期为 $10$。

数据范围

对于所有测试数据，保证：

• $1 \le k \le 50$，$1 \le L \le R \le n \le 10^5$；
• $k \cdot L \le n \le k \cdot R$；
• $1 \le a_i \le 10^6$。

各测试点的约束如下：

• 特殊性质 A：$L = R$。
• 特殊性质 B：$k = 1$。