Maximum Flavor Sum with Limited Adjacent Swaps

Problem Statement:

You are given n pastries, each with a flavor rating. You are allowed to perform at most s swaps on adjacent pastries. In each swap, if the flavor rating of the left pastry is less than that of the right pastry, they are swapped. This operation tends to move higher-rated pastries to the front.

After performing at most s swaps, you must select exactly k pastries such that the sum of their flavor ratings is maximized. If s is large enough (i.e. s \geq n), you can effectively reorder the list arbitrarily and simply choose the k highest ratings. Otherwise, you simulate the swaps as described and then choose the best k pastries from the resulting list.

Examples:

• For n = 5, k = 3, s = 1 and flavors [3, 7, 2, 6, 4], the maximum possible sum is 17.
• For n = 6, k = 4, s = 3 and flavors [1, 9, 3, 4, 8, 7], the maximum possible sum is 28.
• For n = 4, k = 2, s = 2 and flavors [5, 2, 9, 1], the maximum possible sum is 14.

inputFormat

Input Format:

The first line contains three space-separated integers: n (the number of pastries), k (the number of pastries to select), and s (the maximum number of allowed adjacent swaps).

The second line contains n space-separated integers, where each integer represents the flavor rating of a pastry.

outputFormat

Output Format:

Output a single integer representing the maximum possible sum of flavor ratings after performing at most s swaps and selecting k pastries.

## sample

5 3 1
3 7 2 6 4

17

</p>