Problem AA
Postal Delivery

The postal service is interested in cutting costs as an alternative to raising the postage rates. One way to do this is by minimizing the distance traveled when delivering mail from the post office to all the required locations and returning to the post office. It may be that all the mail to be delivered does not fit on the mail truck at once, in which case the distance traveled by the truck must include travel back to the post office to reload. For simplicity, we assume a one dimensional world with the post office at the origin, and delivery locations each identified by a single coordinate. As an example, suppose a postal truck can carry up to $100$ letters and that $50$ letters need to be delivered to location $-10$, that $175$ need to be delivered to location $10$, and $20$ delivered to location $25$. A maximally efficient plan would be:

Deliver the $50$ letters to location $-10$ (travel $2\cdot 10$), the first $100$ letters to location $10$ (travel $2\cdot 10$), the remaining $75$ letters to location $10$ while on the way to delivering the $20$ to location $25$ (travel $2\cdot 25$). The total round-trip distance traveled is $90$.

Input

The first line contains two integers, $N$ and $K$, where $3\le N\le 1000$ is the number of delivery addresses on the route, and $1\le K\le 10000$ is the carrying capacity of the postal truck. Each of the following $N$ lines will contain two integers $x_j$ and $t_j$, the location of a delivery 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 all $j$. All delivery locations are nonzero (that is, none are at the post office).

Output

Output the minimum total travel distance needed to deliver all the letters and return to the post office.

3 100
-10 50
10 175
25 20

90

5 3
-1002 800
-1001 800
-1000 800
-999 800
-998 800

2668000