체크포인트 달리기

시간 제한1초메모리 제한1024 MB

요약

일직선 위 모든 체크포인트를 한 번에 최대 K개씩 체크하며 출발점으로 돌아올 때, 총 이동 거리의 최솟값을 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 동적 계획법
정답자: 아직 제출이 없습니다

문제

철수는 체크포인트 달리기라는 경기에 출전했다. 체크포인트 달리기란 출발점에서 출발하여 길에 있는 모든 체크포인트에 최소 한 번씩 체크하고 출발점으로 돌아오는 경기이다. 출발점은 원점에 있고, 일직선으로 뻗은 길에 $N$ 개의 체크포인트가 있다. $i$ 번째 체크포인트는 좌표 $x\_i$ 에 있다.

체크포인트 달리기에는 특별한 규칙이 있는데, 출발점에서 출발하여 출발점으로 돌아오기 전까지 최대 $K$ 개의 체크포인트에만 체크할 수 있다. 예를 들어 $K$ 가 $3$ 이라면, 출발점에서 출발하여 $3$ 개의 체크포인트를 체크하고, 출발점으로 돌아온 뒤, 다시 다른 체크포인트를 향해 달려가야 한다. 체크포인트를 체크하지 않고 지나칠 수도 있다.

철수가 이동 거리를 최소화하면서 모든 체크포인트를 체크할 수 있게 도와주자.

입력

첫 번째 줄에 체크포인트의 개수 $N$ 과 한 번에 체크할 수 있는 체크포인트의 개수 $K$ 가 주어진다.

이후 $N$ 개의 줄에 체크포인트의 위치 $x\_i$ 가 주어진다.

출력

철수가 이동 거리를 최소화하면서 모든 체크포인트를 체크할 때, 그 이동 거리를 출력한다.

제한

주어지는 모든 수는 정수이다.
$1 \leq N \leq 200\ 000$
$1 \leq K \leq N$
$-10^9 \leq x\_i \leq 10^9$

예제2

예제 1
입력
```
4 2
1
2
3
4
```
예상 출력
```
12
```
예제 2
입력
```
3 1
1
2
3
```
예상 출력
```
12
```