Optimal Placement of Primary Schools

The government is planning to construct a road through a mountainous region. The road passes through n villages exactly once (without forming a loop or crossing), and every pair of adjacent villages is connected by a road with a positive integer distance d_i for 0 < i < n. In addition, the government intends to choose m out of the n villages in which to build primary schools in order to improve the cultural level of the region.

Your task is to determine in which villages to build the primary schools so that the sum of the distances from each village to its nearest primary school is minimized, and then compute the minimum possible sum.

Note: Since the villages are arranged along the road, you can consider the position of the first village as 0, and the position of each subsequent village as the cumulative sum of the distances (pos[i] = pos[i-1] + d_i for i = 2, 3, ..., n).

If m ≥ n, then every village can have a school, and the answer is 0.

Hint: This is a classic dynamic programming problem often known as the 1D k-median or clustering on a line problem. The optimal way to serve a contiguous segment of villages with a single school is to place the school at the median village in that segment (using the fact that the sum of absolute deviations is minimized by the median).

inputFormat

The first line contains two space-separated integers n and m (1 ≤ m ≤ n). The second line contains n-1 space-separated positive integers d1, d2, ..., d_(n-1) representing the distances between adjacent villages.

outputFormat

Output a single integer which is the minimum total sum of distances from each village to the nearest primary school.

sample

5 2
1 2 3 4

7