Background

Ivica has a group consisting of $N$ Croatian companies, but his group is facing difficulties. His businesses have huge debts, so the government sent lawyers to confiscate all his property.

However, we found that although he is deeply in debt, he still reached an agreement with the government and managed to keep some of the companies. Which ones did he keep? We now know.

Problem Description

The lawyers put $N$ debt documents of Ivica’s companies on the table. The debt of the first company is $A_1$, the debt of the second company is $A_2$, and so on.

Ivica reached an agreement with the government so that he can keep all companies corresponding to the documents in the interval $[L, R]$ on the table, but he must take on all debts $A_L, A_{L+1}\ldots A_R$, where $L$ and $R$ are positions among the row of documents on the table.

Fortunately, the lawyers are also corrupt. They can let him swap the documents currently placed at position $i$ and position $j$ for a price of $|i-j|$.

Ivica is a bit desperate. He only has $K$ dollars in his pocket, and he now wants to spend this money here so that the debt he needs to take on is as small as possible.

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 one is $A_i$.

Output Format

Output one integer in one line, the minimum total debt after spending at most $K$ dollars.

3 2 2 1
1 2 3

1

5 2 3 3
21 54 12 2 0

12

6 4 6 100
1 2 3 4 5 6

6

Hint

【Constraints】

For $100\%$ of the testdata, it is guaranteed that $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$.

【Hints and Help】

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

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

Translated by ChatGPT 5