우편 배달

우체국은 우편 요금을 올리는 대신 비용을 줄이는 방법을 찾고 있다. 한 가지 방법은 우체국에서 출발해 필요한 모든 배달지에 우편물을 전달하고 우체국으로 돌아오기까지의 총 이동 거리를 최소화하는 것이다. 배달할 우편물이 트럭에 한 번에 다 실리지 않을 수도 있으므로, 이동 거리에는 다시 싣기 위해 우체국으로 돌아오는 거리도 포함된다.

문제를 단순하게 만들기 위해 세계가 1차원이라고 가정한다. 우체국은 수직선의 원점 $0$에 있고, 각 배달지는 정수 좌표 하나로 나타난다. 트럭은 편지를 한 번에 최대 $K$통까지 싣고, 매번 우체국에서 출발해 우체국으로 돌아온다. 한 번 나갈 때 여러 배달지를 방문해도 되고, 지나가는 배달지에 실은 편지의 일부만 내려놓아도 된다. 이동 거리는 트럭이 수직선 위에서 움직인 거리의 합이다.

트럭 용량이 $100$통이고 좌표 $-10$에 $50$통, 좌표 $10$에 $175$통, 좌표 $25$에 $20$통을 배달해야 하는 경우를 보자. 가장 효율적인 계획은 이렇다. 먼저 $50$통을 좌표 $-10$에 배달한다($2 \times 10 = 20$). 다음으로 $100$통을 좌표 $10$에 배달한다($2 \times 10 = 20$). 마지막으로 좌표 $10$에 남은 $75$통과 좌표 $25$에 갈 $20$통을 함께 싣고 나가, 가는 길에 $75$통을 내려놓고 좌표 $25$까지 갔다 온다($2 \times 25 = 50$). 총 이동 거리는 $90$이다.

모든 편지를 배달하고 우체국으로 돌아오는 데 필요한 최소 총 이동 거리를 구하라.

첫 줄에 두 정수 $N$과 $K$가 주어진다. $N$은 배달지의 수로 $3 \le N \le 1000$이고, $K$는 트럭의 적재 용량으로 $1 \le K \le 10000$이다.

이어지는 $N$개의 줄에는 각각 두 정수 $x_j$와 $t_j$가 주어진다. $x_j$는 배달지의 좌표이고 $t_j$는 그 배달지에 전달할 편지 수이다. 모든 $j$에 대해 $-1500 \le x_1 < x_2 < \cdots < x_N \le 1500$이고 $1 \le t_j \le 800$이다. 배달지 좌표는 모두 $0$이 아니다. 즉 우체국 자리에 있는 배달지는 없다.

모든 편지를 배달하고 우체국으로 돌아오는 데 필요한 최소 총 이동 거리를 한 줄에 출력한다.