Background

The Easy Version and the Hard Version differ only in the final required output; all other descriptions are identical.

Problem Description

youyou is going to hold a contest. There are $n$ problems in this contest, and each problem has a difficulty value $v_i$.

youyou gives a counting parameter $k(k\le n)$. He believes that the solvability $a_x$ of problem $x(x \geq k)$ should be the sum of the difficulty values of the $k$ hardest problems among problems $1 \sim x$, after sorting their difficulty values in nondecreasing order.

Since problems $1 \sim k-1$ are too easy, youyou does not want to consider the solvability of these problems.

So the total solvability of this contest is the sum of the solvability from problem $k$ to problem $n$, i.e., the value of $\sum^{n}_{i=k}a_i$.

youyou can tamper with the difficulty of problem $m$ to any positive integer, but he does not want this contest to be too hard or too easy, so he requires that the total solvability must be within $[l,r]$.

youyou wants to know: by tampering with the difficulty of problem $m$, what is the maximum value the total solvability can be changed to?

In particular, if no solution exists, output $-1$.

Input Format

The first line contains five positive integers: $n,m,k,l,r$.

The second line contains $n$ integers, where the $i$-th number $v_i$ is the difficulty value of problem $i$.

Output Format

Output one number in a single line, representing the maximum total solvability that can be achieved under the constraints.

5 1 1 5 10
1 2 2 2 2

10

Hint

Sample Explanation #1

Since $m=1$, $a_1$ can be tampered with. When $a_1=2$, the total solvability is $2+2+2+2+2=10$. Since $10 \in [5,10]$, the maximum total solvability can be tampered to $10$.

Constraints

This problem uses Subtasks. For each Subtask, you must pass all test points to get the score for that part.

For $100\%$ of the data, $1\le k,m \le n \le 10^5$, $1 \le l \le r \le 10^{9}$, $0\le v_i\le10^9$.

Translated by ChatGPT 5