체크포인트 달리기

면접 대비

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

요약

직선 위의 체크포인트 N개와 한 번에 확인할 수 있는 최대 개수 K가 주어질 때, 모든 체크포인트를 확인하고 원점으로 돌아오는 최소 이동 거리를 구합니다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

철수는 체크포인트 달리기 경기에 출전했다. 체크포인트 달리기는 출발점에서 출발해 길 위의 모든 체크포인트를 최소 한 번씩 체크한 뒤 출발점으로 돌아오는 경기이다. 출발점은 원점에 있고, 일직선으로 뻗은 길 위에 $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
```