Postman

Time limit1sMemory limit512 MB

Summary

Deliver m_i letters to house i at position x_i from the origin, carrying at most k letters per trip, and return to the origin each time; minimize total distance.

Level: Medium6 of 10
Topics: Greedy, Sorting, Math
Solved: No attempts yet

Problem

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.

Input

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$ )

Output

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

Examples2

Example 1
Input
```
4 10
-7 5
-2 3
5 7
9 5
```
Expected output
```
42
```

Example 2

Input

7 1
9400000 10000000
9500000 10000000
9600000 10000000
9700000 10000000
9800000 10000000
9900000 10000000
10000000 10000000

Expected output

1358000000000000