Street

A street has $n$ lots along one side. You want to put up at most $k$ apartment buildings on them. One building covers an interval of at most $t$ consecutive lots, and no two buildings may share a lot.

Lot $i$ carries a height restriction $r_i$. A building may not exceed the restriction of any lot it stands on, so a building covering lots $i$ through $j$ can be at most $H = \min\{r_i, r_{i+1}, \dots, r_j\}$ tall. Its usable facade space is then $H \times (j - i + 1)$.

Pick at most $k$ non-overlapping intervals so that the total usable facade space is as large as possible.

Consider a street of length 10 whose lots carry the restrictions 7, 3, 12, 11, 13, 4, 8, 6, 6, 20.

With $k = 2$ and $t = 4$, the best pick is the intervals $r_3 \dots r_5 = (12, 11, 13)$ and $r_7 \dots r_{10} = (8, 6, 6, 20)$. That is Example 1 in the figure below, and the total usable facade space is $3 \times \min\{12, 11, 13\} + 4 \times \min\{8, 6, 6, 20\} = 57$.

On the same street with $k = 3$ and $t = 4$, the best pick is the intervals $r_3 \dots r_5 = (12, 11, 13)$, $r_7 \dots r_9 = (8, 6, 6)$ and $r_{10} = (20)$. That is Example 2 in the figure, and the total usable facade space is $3 \times \min\{12, 11, 13\} + 3 \times \min\{8, 6, 6\} + 1 \times 20 = 71$.

The first line holds the number of lots $n$, the maximum number of buildings $k$, and the maximum number of lots one building may cover $t$, separated by spaces ($1 \le n \le 500$, $1 \le k \le n$, $1 \le t \le n$). Each of the next $n$ lines holds one height restriction $r_1, r_2, \dots, r_n$, a positive integer at most 100.

Print the largest total usable facade space as a single integer.