K blocks

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

Medium7Dynamic programmingStackSegment treeNo attempts yetTime limit1sMemory limit256 MB

Description

Examples6

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.