P7241 [COCI 2019/2020 #4] Holding

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$ | $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$。 【提示与帮助】 **题目译自 [COCI 2019/2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #4](https://hsin.hr/coci/archive/2019_2020/contest4_tasks.pdf) T3 Holding** 在 COCI 中，本题分值为 $110$ 分。