Ivica 和他的 Holding（他旗下的 $N$ 家克罗地亚公司）正面临着艰难的时刻。这些公司都负债累累，因此国家派出了律师来没收他的一切。我们独家获悉，尽管债务巨大，Ivica 还是成功与国家达成协议，保留了某些公司。是哪些公司呢？我们也查清楚了。
国家律师在桌上摆放了 $N$ 份 Ivica 公司的产权文件。第一家公司的债务写在第一张纸 $A_1$ 上，第二家公司的债务写在 $A_2$ 上，……最后一家公司的债务写在最后一张纸 $A_N$ 上。Ivica 与国家达成的协议是，保留位置在 $L$ 到 $R$ 之间的公司，即 $A_L, A_{L+1}, \dots, A_R$，其中 $L$ 和 $R$ 表示桌上文件数组中的位置。
对 Ivica 来说幸运的是，这些律师（也）是腐败的。他们会强迫他接受协议中约定的连续子区间（即第 $L$ 张到第 $R$ 张文件），但他们允许他以一定的代价交换桌上的任意两张文件。具体来说，交换位置 $i$ 和 $j$ 的文件将花费他 $|i - j|$ 库纳（克罗地亚货币）。Ivica 感到很绝望。他的口袋里只有 $K$ 库纳，他希望通过合理分配这些钱，使得他最终保留的公司的债务总和尽可能小。
请帮助 Ivica 实现他的目标。
输入格式
第一行包含四个空格分隔的整数 $N, L, R$（$1 \le L \le R \le N \le 100$）和 $K$（$0 \le K \le 10\,000$），含义如题面所述。
第二行包含 $N$ 个整数 $A_i$（$0 \le A_i \le 10^6$），表示每家公司的债务。
输出格式
输出一个整数，表示如果 Ivica 最优地使用他的 $K$ 库纳，他最终保留的公司债务总和的最小值。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 22 | $N \le 13$ 且 $R = N$ |
| 2 | 33 | $N \le 50$ 且 $R = N$ |
| 3 | 33 | $N \le 50$ |
| 4 | 22 | 无附加限制 |
样例
输入样例 1
3 2 2 1 1 2 3
输出样例 1
1
输入样例 2
5 2 3 3 21 54 12 2 0
输出样例 2
12
输入样例 3
6 4 6 100 1 2 3 4 5 6
输出样例 3
6