You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Input

The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^4$, $1 \le k \le \min(100, n)$) — the length of the array $a$ and the number of subsegments in the partition.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^4$) — the array $a$.

Output

Print single integer — the minimal weight among all possible partitions.

4 2
6 1 7 4

25

4 3
6 1 7 4

21

5 4
5 1 5 1 5

21

Note

The optimal partition in the first example is next: $6$ $1$ $7$ $\bigg|$ $4$.

The optimal partition in the second example is next: $6$ $\bigg|$ $1$ $\bigg|$ $7$ $4$.

One of the optimal partitions in the third example is next: $5$ $\bigg|$ $1$ $5$ $\bigg|$ $1$ $\bigg|$ $5$.