Postal Delivery

The postal service wants to cut costs instead of raising postage rates. One way is to minimize the distance a truck travels while carrying mail from the post office to every required location and returning to the post office. All the mail may not fit on the truck at once, so the distance traveled also includes the trips back to the post office to reload.

To keep the problem simple, assume a one dimensional world. The post office sits at the origin $0$ of a number line, and each delivery location is a single integer coordinate. The truck carries at most $K$ letters at a time, and every run starts and ends at the post office. A single run may visit several locations, and the truck may drop off only part of its load at a location it passes. The distance traveled is the total distance the truck moves along the number line.

Suppose the truck holds $100$ letters, and $50$ letters go to coordinate $-10$, $175$ letters go to coordinate $10$, and $20$ letters go to coordinate $25$. A maximally efficient plan is this. Deliver the $50$ letters to coordinate $-10$ ($2 \times 10 = 20$). Deliver the first $100$ letters to coordinate $10$ ($2 \times 10 = 20$). Load the remaining $75$ letters for coordinate $10$ together with the $20$ letters for coordinate $25$, drop the $75$ off on the way, and continue out to coordinate $25$ ($2 \times 25 = 50$). The total distance traveled is $90$.

Find the minimum total travel distance needed to deliver every letter and return to the post office.

The first line contains two integers $N$ and $K$. Here $N$ is the number of delivery locations with $3 \le N \le 1000$, and $K$ is the carrying capacity of the truck with $1 \le K \le 10000$.

Each of the following $N$ lines contains two integers $x_j$ and $t_j$, the coordinate of a delivery location and the number of letters to deliver there, where $-1500 \le x_1 < x_2 < \cdots < x_N \le 1500$ and $1 \le t_j \le 800$ for every $j$. No delivery coordinate is $0$, so no location sits at the post office.

Print, on one line, the minimum total travel distance needed to deliver every letter and return to the post office.