SP3791 STREET - Street

There are **n** lots on one side of a street (where **n** k apartment buildings on these lots. Each building must occupy an interval of at most **t** consecutive lots. Moreover, each lot **i** has a height restriction **r\[i\]** (where **r\[i\]** i to **j** is: **H = min{r\[i\], r\[i + 1\], ..., r\[j\]})** Hence, the maximum usable facade space of the building is: **H × (j − i + 1)**. We would like to have a program to select at most **k** non-overlapping intervals to erect the buildings such that the total usable facade space is maximized.

The input file is as follows: The first line contains three integers **n**, **k**, and **t** separated by a space character, where 1 n k t nlines contain **n** positive integers representing the height restriction for the **n** lots. For Example 1, the input file looks like: ``` 10 2 4 7 3 12 11 13 4 8 6 6 20 ``` The input should be read from the standard input, and your program will be run several times, each one with one of the test cases.

The output file contains an integer which is the maximum usable facade space. For the above example, the output file looks like: ``` 57 ``` - - - - - - [National Olympiad in Informatics (NOI) - 2007](http://www.comp.nus.edu.sg)