Description

The government has built a single road in a mountainous area that passes through each of the $n$ villages exactly once, with no cycles or intersections. Any two villages can communicate only along this road. The distance between any two adjacent villages is $d_i$ (each $d_i$ is a positive integer), where $1 \le i < n$. To improve education in the area, the government will choose $m$ out of the $n$ villages to build primary schools. Given $n$, $m$, and the distances between all adjacent villages, decide in which villages to build the primary schools so that the sum of distances from all villages to their nearest primary school is minimized, and compute this minimum value.

Input Format

The first line contains $n$ and $m$, separated by a space. The second line contains $n-1$ integers, in order from one end to the other, representing the distances between adjacent villages, separated by spaces.

For example

10 3
2 4 6 5 2 4 3 1 3

means building $3$ primary schools among $10$ villages. The distance between village $1$ and village $2$ is $2$, between village $2$ and village $3$ is $4$, between village $3$ and village $4$ is $6$, ..., and between village $9$ and village $10$ is $3$.

Output Format

Output the minimal sum of distances from all villages to their nearest primary school.

10 2
3 1 3 1 1 1 1 1 3

18

Hint

$1 \le m \le n < 500$, $1 \le d_i \le 100$.

Translated by ChatGPT 5