COCI '19 Contest 4 #3 Holding

Points: 15 (partial)

Time limit: 2.0s

Memory limit: 256M

Problem type

Difficult times lie ahead of Ivica and his Holding – a group of $N$ ~N~ Croatian companies that are in his ownership. Each of these companies is in debt so the state sent its attorneys to take everything away from him. We have exclusively found out that Ivica managed to make a deal with the state to leave him certain companies in spite of the massive debt. Which ones? We found that out as well.

The state attorneys have laid out $N$ ~N~ proprietary papers of Ivica's companies on the table. The debt of first company is written on the first paper $A_1$ ~A_1~, the debt of the second company is written on $A_2$ ~A_2~, … and the debt of the last company is written on the last paper $A_N$ ~A_N~. Ivica made a deal with the state to leave the companies $A_L, A_{L+1}, \dots, A_R$ ~A_L, A_{L+1}, \dots, A_R~ in his ownership, where $L$ ~L~ and $R$ ~R~ represent the positions in an array of papers on the table. Fortunately for Ivica, the attorneys are (also) corrupt. They will force him to take the same contiguous subarray as agreed upon (from $L$ ~L~-th to $R$ ~R~-th paper), but they will let him swap any two papers on the table for a specific cost. More precisely, swapping papers at positions $i$ ~i~ and $j$ ~j~ will cost him $|i-j|$ ~|i-j|~ kunas (Croatian currency). Ivica is desperate. He has only $K$ ~K~ kunas in his pocket which he now wishes to spend in such a way that the sum of debts of companies he is left with is as small as possible.

Help Ivica achieve his goal.

Input

The first line contains four space-separated integers $N, L, R$ ~N, L, R~ $(1 \le L \le R \le N \le 100)$ ~(1 \le L \le R \le N \le 100)~ and $K$ ~K~ $(0 \le K \le 10\,000)$ ~(0 \le K \le 10\,000)~ from the task description.

The second line contains $N$ ~N~ integers $A_i$ ~A_i~ $(0 \le A_i \le 10^6)$ ~(0 \le A_i \le 10^6)~ from the task description.

Output

You should output a single integer which represents the smallest amount of total debt Ivica will have if he spends his $K$ ~K~ kunas optimally.

Scoring

Subtask	Score	Constraints
$1$ ~1~	$22$ ~22~	$N \le 13$ ~N \le 13~ and $R=N$ ~R=N~
$2$ ~2~	$33$ ~33~	$N \le 50$ ~N \le 50~ and $R=N$ ~R=N~
$3$ ~3~	$33$ ~33~	$N \le 50$ ~N \le 50~
$4$ ~4~	$22$ ~22~	No additional constraints.

Sample Input 1

3 2 2 1
1 2 3

Sample Output 1

Sample Input 2

5 2 3 3
21 54 12 2 0

Sample Output 2

Sample Input 3

6 4 6 100
1 2 3 4 5 6

Sample Output 3

Comments

There are no comments at the moment.