暂无测试数据。

Description

\(\text{Scarral}\)沿着神秘小道建立了一排共 \(n\) 个枪房，第 \(i\) 号枪房里有 \(a_i\) 个特种枪。正在\(\text{Scarral}\)期待这些枪能派上用场的时候，强盗头子\(\text{Volt}\)来了。\(\text{Volt}\)拿着手枪指着\(\text{Scarral}\)的脑袋，告诉\(\text{Scarral}\) \(10\)天之内必须把第 \(L\) 号到 \(R\) 号位置枪房里的枪支全部送运走。\(\text{Scarral}\)当然不敢违抗\(\text{Volt}\)的命令，但是因为\(\text{Scarral}\)发现\(\text{Volt}\)并没有去清点每间枪房里枪支的个数，所以\(\text{Scarral}\)在\(\text{Volt}\)再次到来之前决定采取“交换枪房”的行动。因为每一个枪房里里面的枪支都不互相干扰，而不同枪房的枪支不能直接放入一个枪房中。将两个枪房里的枪支整体交换是需要运费的，每次交换两个枪房的枪支需要的运费就是这两个枪房的距离（例如：第 \(i\) 号枪房和第 \(j\) 号枪房（\(i<j\)）的枪支交换，那么需要的运费就是 \(j-i\)）。现在\(\text{Scarral}\)手里有 \(K\) 元钱，枪房可以多次交换，但是总的费用不能超过 \(K\)。那么请你帮忙计算一下，等\(\text{Volt}\)再次到来时，\(\text{Scarral}\)交给\(\text{Volt}\)的枪支总数最少是多少？

---

Input

第 \(1\) 行 \(4\) 个正整数，分别表示 \(N\)，\(L\)，\(R\)，\(K\)。
第 \(2\) 行 \(n\) 个整数，表示每个枪房里特种枪的个数。

---

Output

\(1\) 行 \(1\) 个正整数，表示 \(\text{Scarral}\) 交给 \(\text{Volt}\) 的最少枪支数。

---

Sample

Sample input

#1

3 2 2 1
1 2 3

#2

5 2 3 3
21 54 12 2 0

#3

6 4 6 100
1 2 3 4 5 6

Sample output

#1

1

#2

12

#3

6

---

Hint

对于 \(20\%\) 的数据 \(1\le N\le 13\)；\(R=N\)；
对于 \(50\%\) 的数据 \(1\le N\le 50\)；
对于所有的数据 \(1\le N\le 100\)；\(1\le L\le R\le N\)；\(0\le K\le 10000\)；\(0\le a_i\le 1000000\)。