Description

The government has constructed a road in a certain mountainous area, passing through a total of $m$ villages exactly once without any loops or intersections. Any two villages can only travel via this road. The distance between any two adjacent villages is given as $d_i$ (a positive integer), where $0 < i < m$. To improve the cultural and educational standards in the mountainous area, the government has decided to select $n$ villages out of the $m$ villages to build primary schools (where $0 < n \leq m < 500$). Given the values of $m$, $n$, and the distances between all adjacent villages, determine which villages should be selected to build primary schools so that the total distance from all villages to their nearest primary school is minimized. Compute this minimum value.

Input Format

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

For example:

10 3
2 4 6 5 2 4 3 1 3

Indicates building 3 schools in 10 villages. The distance between the 1st village and the 2nd village is 2, between the 2nd and 3rd villages is 4, between the 3rd and 4th villages is 6, ..., and between the 9th and 10th villages is 3.

Output Format

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

10 3
2 4 6 5 2 4 3 1 3

10 2
3 1 3 1 1 1 1 1 3