Postman

A postman delivers letters to the houses of a one-dimensional world.

The post office holds every letter at the start and sits at coordinate $x = 0$. There are $n$ houses that need mail. House $i$ sits at coordinate $x_i$ and needs $m_i$ letters. The postman carries at most $k$ letters at a time.

The postman starts at the post office, picks up any number of letters up to his carrying capacity, visits some of the houses and drops letters off, then returns to the post office. He repeats this until every letter is delivered, and he ends at the post office. The letters for one house may be carried over several trips.

The postman moves one unit of distance in one unit of time.

Find the minimum time the postman needs to start at the post office, deliver every letter, and return to the post office.

The first line contains two space separated integers $n$ and $k$. ($1 \le n \le 1000$, $1 \le k \le 10^7$)

Each of the next $n$ lines contains two space separated integers $x_i$ and $m_i$. ($|x_i| \le 10^7$, $1 \le m_i \le 10^7$)

Print on a single line the minimum time needed to deliver every letter and return to the post office.