84427 - Holding

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

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

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

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

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

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

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

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

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

【数据规模与约定】

对于 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 #4