EIU Programming Practices and Exams

"giaohangtocdo.vn" is a start-up company. Every day, the company delivers many kinds of products for n retail stores, called 1, 2...n. All stores are located on a long street: store i at position pi on that street.

For simplicity, we assume that all kinds of products have the same size, same weight, and store i needs a fixed number ni products each day.

The company uses many trucks to deliver products. Each truck can bring maximum k products. A truck can also deliver products for some stores in a trip. The company plans to build a grand-warehouse where all trucks pick up products and start a trip to the stores. They want to choose a location on the street to build the grand-warehouse to optimize the total distance of all trips in a day.

Input

+ The first line contains integer numbers n (1 < n < 10^5) and k (0 < n < 10^9)

+ There are n lines after that, where line i contains data for store i, that are pi (0 < pi < 10^9) and ni (0 < ni < 10^9) respectively

Output

Print the total distance of all trips (one-way delivery) in a day

Example

Input

6 5

1 7

2 2

3 6

8 9

10 11

15 13

Output

44