Building Primary Schools in the Mountains

Problem Background

Special for beginners, ^_^

Problem Description

The government built a road in a mountainous area that passes through each of $m$ villages exactly once, with no loops or crossings, so any two villages can only reach each other via this road. The distance between any two adjacent villages is $d_i$ (a positive integer), where $0 < i < m$. To improve cultural quality in the mountains, the government also decided to build primary schools in $n$ of the $m$ villages (assume $0 < n \le m < 500$). Given $m, n$ and the distances between all adjacent villages, choose which villages to build schools in so that the sum of distances from every village to its nearest school is minimized, and compute that minimum value.

Input Format

The first line contains $m$ and $n$, separated by a space.

The second line contains $m - 1$ integers, giving the distances between adjacent villages from one end to the other, separated by spaces.

For example:

10 3
2 4 6 5 2 4 3 1 3

means building $3$ 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

The minimum sum of distances from every village to its nearest school.

Sample Input

10 2
3 1 3 1 1 1 1 1 3

Sample Output

18

Constraints

1s, 1024KiB for each test case.