题目背景

Ivica 有一个由 $N$ 家克罗地亚公司组成的集团，但他的集团正面临着困难。他的企业承受着觉的负债，所以政府派遣律师没收了他的一切财产。

但我们发现，尽管他有巨额债务在身，他依然与政府达成协议，留住了部分企业。他留住的是哪些？我们也知道了。

题目描述

律师们把 Ivica 的公司的 $N$ 份债务文件摆在桌上。第一家公司的债务为 $A_1$ ，第二家公司的债务为 $A_2$ ，依次类推。

Ivica 与政府达成协议，使它留下桌上 $[L,R]$ 区间的所有文件所对应的公司，但他需要承担 $A_L,A_{L+1}\ldots A_R$ 的所有债务，其中 $L$ 和 $R$ 代表桌子上一系列文件中的位置。

幸运的是，律师们也是腐败。他们可以让他以 $|i-j|$ 的价格交换当前放在位置 $i$ 和位置 $j$ 的文件。

Ivica 有点绝望。他口袋里只有 $K$ 元钱，他现在想把这些钱花在这里，使得他的需要承担的债务尽可能少。

请帮他达成目标。

输入格式

第一行四个整数 $N,L,R,K$。

第二行 $N$ 个整数，第 $i$ 个表示 $A_i$。

输出格式

一行一个整数，表示花不超过 $K$ 元后负债的最小值。

3 2 2 1
1 2 3

1

5 2 3 3
21 54 12 2 0

12

6 4 6 100
1 2 3 4 5 6

6

提示

【数据规模与约定】

对于 $100\%$ 的数据，保证 $1\le N\le 100$，$1\le L\le R\le N$，$1\le K\le 10^4$，$1\le A_i\le 10^6$。

【提示与帮助】

题目译自 COCI 2019/2020 CONTEST #4 T3 Holding

在 COCI 中，本题分值为 $110$ 分。