Cafeteria Queue
By Marcio Oshiro, USP 
Brazil
By Marcio Oshiro, USP Brazil
A very common phenomenon in line at the cafeteria (also known as university restaurant) is to see a person trying to infiltrate in the middle of the queue instead of at the end. This is where this person finds someone in your group already in the queue.
Interested in studying this phenomenon, a friend asked you to write a program to study the groups present in the queue. We can assume that there are K different groups and every person belongs to exactly one of these groups. The size of a group is defined by the distance between the two most distant people in the group. If the group consists of only one person, its size is zero. Whereas the groups are organized so that the sum of the sizes of the K groups is minimal, your program must determine what is the value of this sum.
The input consists of several test cases and ends with end of file (EOF). The first line of each test case contains the integer N indicating the number of people in line, and K, indicating the number of groups (1 ≤ K <N ≤ 1.000). In the next line are presented N - 1 integers, a2, ... , AN, (0 ≤ a2 ≤ · · · ≤ aN ≤ 1,000,000) indicating the positions of each person to the first person in line. The position of the first person is omitted since it is always zero.
For each test case, print one line containing the minimum value that the sum of the sizes of the K groups can have.
| Sample Input | Sample Output |
|
5 2 |
3 |