Maximizing Contest Solvability Under Difficulty Modification

You are given a contest with n problems. The i-th problem has an initial difficulty \(v_i\). For any prefix of the problems from 1 to x (with \(x\ge k\)), define its solvability \(a_x\) as the sum of the k largest difficulties among the first \(x\) problems (i.e. after sorting \(v_1,v_2,\dots,v_x\) in increasing order, take the sum of the largest k values). The total contest solvability is defined as \[ S = \sum_{x=k}^{n} a_x. \]

You are allowed to modify exactly m problems – that is, you may choose m indices and change the difficulty of each chosen problem to any positive integer. However, to avoid making the contest too easy or too hard, the final total solvability must lie within the interval ([l, r]). Under these conditions, you want to maximize the total solvability. More precisely, if it is possible to adjust the difficulties so that (S) lies in ([l, r]), what is the maximum total solvability you can achieve? It is guaranteed that by increasing some modified difficulties appropriately (or leaving them as low as possible), every value in some interval ([S_{min}, \infty)) is attainable. In particular, if the minimum possible total solvability obtainable by an optimal choice of modifications exceeds (r), then no valid solution exists and you should output -1. Otherwise, the answer is (r) (because you can always tune the modified values to hit any target up to (r)).

Note: To compute the minimum achievable total solvability \(S_{min}\), note that you can choose m problems to modify and set their difficulties to 1 (the minimum allowed value). Then, by simulating the definition of \(S\) (using a running prefix and picking the k largest values in each prefix), you get \(S_{min}\). If \(S_{min} > r\), then output -1; otherwise, the maximum total solvability you can achieve subject to \(S \in [l, r]\) is r.

Input Format:

• The first line contains five integers: \(n, k, m, l, r\).
• The second line contains \(n\) positive integers \(v_1, v_2, \ldots, v_n\), representing the initial difficulties.

Output Format:

• Output a single integer, which is the maximum achievable total solvability that lies within \([l, r]\). If no valid configuration exists, output -1.

inputFormat

The input consists of two lines.

• First line: five integers n, k, m, l, r separated by spaces.
• Second line: n integers representing \(v_1, v_2, \ldots, v_n\) separated by spaces.

outputFormat

Output a single integer – the maximum achievable total contest solvability under the restriction that it lies in \([l, r]\), or -1 if no valid configuration exists.

sample

3 2 1 10 100
5 2 8

100