Coin Quiz

The rules of a new TV quiz are as follows. There are $n$ cells in a row, numbered from $1$ to $n$. Cell $i$ contains $a_i$ coins.

A player may choose an integer $b$ and pay $b$ coins. Then the host takes the coins from every cell that holds at most $b$ coins, and those cells become empty. After that, among any $k$ consecutive cells there must be at least $m$ empty cells. Then the player takes all coins left on the board. If the player takes $a$ coins in total, the prize is $a-b$.

Find the maximum prize the player can guarantee.

The first line contains integers $n$, $k$, and $m$ ($1 \le m < k \le n \le 200000$).

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$).

Print one integer: the maximum prize the player can guarantee.

In the first example, the player chooses $b = 5$. After the coins are removed from the cells that hold at most $5$ coins, the cells contain $[0, 7, 0, 0, 0, 9, 0, 6]$. The player takes $22$ coins from the cells. Counting the $5$ coins paid earlier, the prize is $17$.

In the second example, so that every two consecutive cells contain at least one empty cell, the player must choose $b = 2$. After that no coins remain, and the prize is negative: $-2$.