K blocks

Time limit1sMemory limit256 MB

Summary

Split the array into exactly K contiguous blocks so the sum of each block's maximum is as small as possible.

Level: Medium7 of 10
Topics: Dynamic programming, Stack, Segment tree
Solved: No attempts yet

Problem

You are given a sequence $A$ of $N$ positive integers. Split the sequence into exactly $K$ blocks. A block is a non-empty run of consecutive elements, and every element belongs to exactly one block.

The value of a split is the sum of the largest element of each of the $K$ blocks. For the given $K$ , find the smallest value a split can have.

Input

The first line contains two integers $N$ and $K$ ( $1 \le K \le N \le 2000$ ).

The second line contains $N$ integers $A_1, A_2, \ldots, A_N$ ( $1 \le A_i \le 10^6$ ), the elements of the sequence.

Output

Print one integer, the smallest possible value of a split into $K$ blocks.

Examples6

Example 1
Input
```
5 1
1 2 3 4 5
```
Expected output
```
5
```
Example 2
Input
```
5 2
1 2 3 4 5
```
Expected output
```
6
```
Example 3
Input
```
1 1
1000000
```
Expected output
```
1000000
```
Example 4
Input
```
5 5
1 2 3 4 5
```
Expected output
```
15
```
Example 5
Input
```
5 2
5 4 3 2 1
```
Expected output
```
6
```
Example 6
Input
```
6 3
7 7 7 7 7 7
```
Expected output
```
21
```