题目背景

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

在 COCI 中，本题分值为 \(110\) 分。

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\) 元后负债的最小值。

样例1

样例输入1

3 2 2 1
1 2 3

样例输出1

1

样例2

样例输入2

5 2 3 3
21 54 12 2 0

样例输出2

12

样例3

样例输入3

6 4 6 100
1 2 3 4 5 6

样例输出3

6

限制

子任务编号	特殊限制	分值
\(1\)	\(N\le 13\)，\(R=N\)	\(20\)
\(2\)	\(N\le 50\)，\(R=N\)	\(30\)
\(3\)	\(N\le 50\)	\(30\)
\(4\)	无特殊限制	\(20\)

对于 \(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\)。