Holding
Time limit2sMemory limit256 MB
You may swap any two positions at cost equal to their distance; with budget K, minimize the sum of values in the fixed segment [L, R].
- Level
Medium7 of 10
- Topics
- Greedy, Sorting, Implementation, Brute force
- Solved
- No attempts yet
Problem
Difficult times lie ahead of Ivica and his Holding, a group of N Croatian companies that he owns. 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 proprietary papers of Ivica's companies on the table. The debt of the first company is written on the first paper A1, the debt of the second company is written on A2, ..., and the debt of the last company is written on the last paper AN. Ivica made a deal with the state to leave the companies AL, AL+1, ..., AR in his ownership, where L and 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 the L-th to the R-th paper), but they will let him swap any two papers on the table for a specific cost. More precisely, swapping the papers at positions i and j will cost him |i − j| kunas (Croatian currency). Ivica is desperate. He has only K kunas in his pocket, which he now wishes to spend in such a way that the sum of debts of the 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 (1 ≤ L ≤ R ≤ N ≤ 100) and K (0 ≤ K ≤ 10 000) from the task description.
The second line contains N integers Ai (0 ≤ Ai ≤ 106) from the task description.
Output
Output a single integer, the smallest total debt Ivica will have if he spends his K kunas optimally.