Zero Subarray Problem

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Given three integers \(n\), \(m\), and \(k\). Also, an array \(a\) of length \(n\) is given.

You can perform two types of operations:

1. Choose two indices \(i\) and \(j\) (\(i \neq j\)) and swap the elements \(a_i\) and \(a_j\). This operation can be performed at most \(k\) times.

2. Decrease any array element by \(1\), if it is greater than \(0\). This operation can be performed any number of times.

Zenyk performs these operations in any order and wants to ensure that after all operations there is a subarray of length \(m\) consisting entirely of zeros.

Input

The first line contains three integers \(n\), \(m\), and \(k\) — the length of the array, the length of the subarray that Zenyk wants to zero out, and the maximum number of operations of the first type.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) — the elements of the array.

Output

Output a single number — the minimum number of operations of the second type required to form a subarray where all elements are equal to zero.

Constraints

\(1 \le m \le n \le 4 \cdot 10^5\),

\(1 \le k \le 4 \cdot 10^5\),

\(1 \le a_i \le 10^9\).

Scoring consists of the following blocks:

• 1 point for each example from the statement,

• 8 points: \(n \le 2000, k = 1\),

• 14 points: \(m \le k\),

• 17 points: \(n \le 10^5, k \le 10\),

• 24 points: \(n, k \le 10^5\),

• 35 points: no additional constraints.

You will receive points for a block only if your program passes all tests in that block.

Samples

Input (stdin) сopy	Output (stdout) сopy
7 3 2 1 2 5 2 4 4 6	5

Input (stdin) сopy	Output (stdout) сopy
5 2 1 1 4 4 6 2	3

Notes

In the first example:

We use the operation of the first type and swap the elements at indices \(3\) and \(4\).

After that, we take the subarray of length \(3\) from the first three elements, it looks like this: [1, 2, 2]

To make all its elements equal to zero, we use operations of the second type. This requires 5 operations.

This is the optimal answer for this example.