Description

You are the host of the restaurant Wagnaria. Some rainy day, because of the broken roofs, there are n dripping positions. You need to put some bowls to catch the rain. So, you order k employees to clean the bowls at every moment. Every employee will put the large trashcan to a best position. At every moment, he will take an empty bowl to some bowl’s location assigned to him to swap the empty bowl and bowl filled of water. You want these employees to find the best allocation. Please write a program to minimize the total distance every employee needs to walk.

For example, there are 9 dripping location {1, 2, 3, 7, 8, 9, 13, 14, 15} and 3 employees.
The best allocation is:
Employee 1 is at position 2. Employee 2 is at position 8. Employee 3 is at position 14.
Then the actions of the employee 1:
1. Take an empty bowl to the bowl 1 to swap the two bowls. (Distance: 1)
2. Go to the position of the employee 1’s trashcan to throw rain in the bowl. (Distance: 1)
3. Take an empty bowl to the bowl 2 to swap the two bowls. (Distance: 0)
4. Go to the position of the employee 1’s trashcan to throw rain in the bowl. (Distance: 0)
5. Take an empty bowl to the bowl 3 to swap the two bowls. (Distance: 1)
6. Go to the position of the employee 1’s trashcan to throw rain in the bowl. (Distance: 1)
The total distance employee 1 needs to walk is 4. The total minimize distances all employee need to walk is 12.
To simplify this problem, the employees can ONLY put the trashcan at the position with integer number.

Input

Each test case starts with a line containing two integers n(1 ≤ n ≤ 1000) and k (1 ≤ k ≤ 1000) indicating the number of the dripping positions and the number of employees. Following this is one line, containing n integers x_i specifies the dripping position.
1 ≤ x₁ < x₂ < x₃ < ⋯ < x_n ≤ 1000

Output

Output the minimum total distance all employees need to walk.

Sample Input  Download

Sample Output  Download

Tags

Discuss