거리

거리 한쪽에 부지가 $n$개 늘어서 있다. 이 부지 위에 아파트를 최대 $k$채까지 세우려고 한다. 아파트 한 채는 연속한 부지를 $t$개 이하로 차지하고, 두 아파트가 같은 부지를 함께 쓸 수는 없다.

부지 $i$에는 높이 제한 $r_i$가 걸려 있다. 아파트는 자기가 올라선 부지의 높이 제한을 하나도 넘을 수 없으므로, 부지 $i$부터 $j$까지를 차지하는 아파트의 높이는 최대 $H = \min\{r_i, r_{i+1}, \dots, r_j\}$이다. 이때 아파트의 사용 가능한 전면 면적은 $H \times (j - i + 1)$이다.

서로 겹치지 않는 구간을 최대 $k$개 골라 사용 가능한 전면 면적의 합을 최대로 만들어라.

길이가 10인 거리를 보자. 부지의 높이 제한은 차례대로 7, 3, 12, 11, 13, 4, 8, 6, 6, 20이다.

$k = 2$, $t = 4$라면 구간 $r_3 \dots r_5 = (12, 11, 13)$과 $r_7 \dots r_{10} = (8, 6, 6, 20)$을 고르는 것이 최선이다. 아래 그림의 Example 1이 이 배치이고, 사용 가능한 전면 면적의 합은 $3 \times \min\{12, 11, 13\} + 4 \times \min\{8, 6, 6, 20\} = 57$이다.

같은 거리에서 $k = 3$, $t = 4$라면 구간 $r_3 \dots r_5 = (12, 11, 13)$, $r_7 \dots r_9 = (8, 6, 6)$, $r_{10} = (20)$을 고르는 것이 최선이다. 그림의 Example 2가 이 배치이고, 사용 가능한 전면 면적의 합은 $3 \times \min\{12, 11, 13\} + 3 \times \min\{8, 6, 6\} + 1 \times 20 = 71$이다.

첫째 줄에 부지의 수 $n$, 아파트의 최대 개수 $k$, 아파트 한 채가 차지할 수 있는 최대 부지 수 $t$가 공백을 사이에 두고 주어진다 ($1 \le n \le 500$, $1 \le k \le n$, $1 \le t \le n$). 이어지는 $n$개 줄에는 각 부지의 높이 제한 $r_1, r_2, \dots, r_n$이 한 줄에 하나씩 주어진다. 높이 제한은 100 이하의 양의 정수이다.

사용 가능한 전면 면적의 합을 최대로 만들었을 때 그 합을 정수 하나로 출력한다.