Problem Background

Ivica has a group consisting of $N$ Croatian companies, but his group is facing difficulties. His enterprises are burdened with significant debts, so the government has sent lawyers to seize all his assets.

However, we have discovered that despite his massive debts, he has still managed to reach an agreement with the government to retain some of his companies. We know which ones he has retained.

Problem Description

The lawyers have laid out $N$ debt documents for Ivica's companies on a table. The debt of the first company is $A_1$, the second company is $A_2$, and so on.

Ivica has reached an agreement with the government to retain all companies corresponding to the documents in the range $[L, R]$ on the table, but he needs to bear all the debts $A_L, A_{L+1} \ldots A_R$, where $L$ and $R$ represent positions in a series of documents on the table.

Fortunately, the lawyers are also corrupt. They allow him to exchange the documents currently at positions $i$ and $j$ for a price of $|i-j|$.

Ivica is desperate. He only has $K$ dollars in his pocket, and he wants to spend this money to minimize the debt he needs to bear.

Please help him achieve this goal.

Input Format

The first line contains four integers $N, L, R, K$.

The second line contains $N$ integers, where the $i$-th integer represents $A_i$.

Output Format

A single line containing one integer, representing the minimum debt value after spending no more than $K$ dollars.

Sample Input and Output

Sample Input #1

3 2 2 1
1 2 3

Sample Output #1

1

Sample Input #2

5 2 3 3
21 54 12 2 0

Sample Output #2

12

Sample Input #3

6 4 6 100
1 2 3 4 5 6

Sample Output #3

6

Notes

Data Constraints

For $100\%$ of the data, it is guaranteed that $1 \le N \le 100$, $1 \le L \le R \le N$, $1 \le K \le 10^4$, and $1 \le A_i \le 10^6$.

Hints and Help

This problem is translated from COCI 2019/2020 CONTEST #4 T3 Holding

In COCI, this problem is worth $110$ points.

见题面 Input 部分

见题面 Output 部分