题目描述

译自 COCI 2019/2020 Contest #4 T3「Holding」

Ivica 和他的资产——一个他拥有的，由 $N$ 个克罗地亚企业组成的财团，正在经历一段困难的时间。每家企业都有负债，所以政府派公职律师拿走他的一切财产。只有我们发现了尽管他有着巨额的欠债，Ivica 还是成功地让政府留给他了某些企业。是哪些呢？我们也知道了。

公职律师在桌子上摆出了 $N$ 份 Ivica 的公司的专有文件。第一个公司的债务数额写在第一份文件上，数额是 $A_1$，第二个公司的债务数额写在第二份文件上，数额是 $A_2$，……，最后一家公司的债务数额写在最后一份文件上，数额是 $A_N$。Ivica 成功留下了公司 $A_L,A_{L+1},\ldots ,A_R$，这里 $L,R$ 表示桌子上文件的位置。Ivica 很幸运，因为公职律师（也）是腐败的。他们会让他拿走编号从 $L$ 到 $R$ 的文件，但是他们会让他以特定的代价交换任意两份文件。更确切地说，交换位置 $i$ 和 $j$ 的文件会花费 $|i-j|$ 库纳（克罗地亚货币）。Ivica 目前很绝望，他口袋里只有 $K$ 库纳，他想要使得留下的公司负债越少越好。

请帮他达成目标。

一句话题意

给定一个长为 $N$ 的数组 $A$，可以多次交换两个数的位置，代价为两个位置下标差的绝对值。现在给定 $L,R$，求在代价和不超过 $K$ 的情况下，$A$ 数组中 $[L,R]$ 的区间和的最小值。

输入格式

第一行四个整数 $N,L,R,K$，意义同题目描述；

第二行 $N$ 个整数 $A_i$，意义同题目描述。

输出格式

输出一行一个整数，表示最优情况下花 $K$ 库纳能够留下公司的最小负债钱数。

样例 1

输入

3 2 2 1
1 2 3

输出

1

样例 2

输入

5 2 3 3
21 54 12 2 0

输出

12

样例 3

输入

6 4 6 100
1 2 3 4 5 6

输出

6

数据范围与提示

对于全部数据，$1\le L\le R\le N\le 100,0\le K\le 10^4,0\le A_i\le 10^6$。

详细子任务附加限制及分值如下表：

子任务编号	附加限制	分值
1	$N\le 13,R=N$	20
2	$N\le 50,R=N$	30
3	$N\le 50$
4	无附加限制	20