Checkpoint running

Interview

Time limit1sMemory limit1024 MB

Summary

Given N checkpoint positions on a line and a trip limit K, find the minimum total distance to visit all checkpoints, returning to the origin after each trip of at most K checkpoints.

Level: Medium5 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

Chulsoo entered a checkpoint running race. In this race, a runner starts at the starting point, checks every checkpoint on the road at least once, and returns to the starting point. The starting point is at the origin, and $N$ checkpoints are placed on a straight road. The $i$ -th checkpoint is at coordinate $x_i$ .

The race has a special rule. Before returning to the starting point, a runner can check at most $K$ checkpoints. For example, if $K$ is $3$ , a runner starts from the starting point, checks $3$ checkpoints, returns to the starting point, and then runs toward another checkpoint. A runner may also pass a checkpoint without checking it.

Help Chulsoo check all checkpoints while minimizing the total distance traveled.

Input

The first line contains the number of checkpoints $N$ and the maximum number of checkpoints $K$ that can be checked in one trip.

The next $N$ lines each contain the position $x_i$ of a checkpoint.

Output

Print the minimum total distance Chulsoo must travel to check all checkpoints.

Constraints

All given numbers are integers.

$1 \leq N \leq 200\,000$
$1 \leq K \leq N$
$-10^9 \leq x_i \leq 10^9$

Examples2

Example 1
Input
```
4 2
1
2
3
4
```
Expected output
```
12
```
Example 2
Input
```
3 1
1
2
3
```
Expected output
```
12
```