Minimizing Debt with Limited Swap Budget

Ivica faces a difficult situation. His company’s N debt files are laid out on a table in a fixed order. The i-th file has a debt amount \(A_i\). Due to a government decree, he must keep (and later pay for) all the companies corresponding to the files in a fixed contiguous segment \([L,R]\) (1-indexed). In other words, without any changes, his debt will be

[ S_0 = \sum_{i=L}^{R} A_i. ]

Fortunately—and nefariously—the lawyers are corrupt. They allow him to swap the files at two positions \(i\) and \(j\) at a price of \(|i-j|\) (in monetary units). Ivica has a budget of \(K\) units to spend on such swaps. When he swaps a file from inside the interval \([L,R]\) with a file from outside (either from positions \(1\) to \(L-1\) or from \(R+1\) to \(N\)), the file coming from outside replaces a file in the interval and therefore the debt at that position changes. Naturally, if the outside file has a lower debt than the one inside, his total debt will drop.

The task is to help Ivica minimize his eventual debt S (the sum of the debts in positions \([L,R]\) after his swaps) by judiciously choosing a set of swap operations whose total cost does not exceed \(K\). Note that every swap operation involves two files. If a file originally inside \([L,R]\) (with debt \(A_i\)) is exchanged with a file from outside (with debt \(A_j\)), then the new contribution of that position becomes \(A_j\) (and the file with \(A_i\) goes outside and does not affect Ivica’s liability). Thus the improvement (debt reduced) by that swap is \(A_i - A_j\) (this swap is only beneficial if \(A_i > A_j\)).

You may assume that any matching (i.e. no file is used more than once) between an inside file and an outside file is allowed, and that an optimal solution can be found among non‐crossing pairings (i.e. if you list the indices in increasing order, you may assume that the pairs occur in order).

More formally, let \(I = \{L,L+1,\ldots,R\}\) be the set of positions in the block you must keep, and let \(O\) be the set of positions outside \([L,R]\). For any swap pairing of an index \(i \in I\) with an index \(j \in O\) (allowed only if \(A_i > A_j\)), the cost is \(|i-j|\) and the benefit is \(A_i - A_j\). You are to choose a set of disjoint pairs such that the total swap cost is at most \(K\) and the total benefit is maximized. The final answer is then

[ S = S_0 - \text{(maximum total benefit)}. ]

Help Ivica to achieve the minimum possible final debt S.

inputFormat

The first line of input contains four integers: \(N\), \(L\), \(R\) and \(K\) (1 ≤ L ≤ R ≤ N). The second line contains \(N\) integers \(A_1, A_2, \ldots, A_N\) representing the debt amount on each file.

All indices are 1-indexed.

outputFormat

Output a single integer: the minimum total debt Ivica must bear for the files in positions \([L,R]\) after performing swaps with total cost at most \(K\).

sample

5 2 4 1
10 7 5 8 6

18