Để trở thành bưu điện thân thiện với môi trường, bưu điện thành phố Straightland muốn cắt giảm lượng xăng cần sử dụng cho các xe đưa thư của mình, cụ thể là cắt giảm tổng quãng đường đưa toàn bộ thư của mình đến các địa điểm trong thành phố và quay trở lại bưu điện. Do lượng thư cần chuyển trong bưu điện có nhiều mà sức chứa của xe đưa thư lại có hạn, xe đưa thư có thể phải quay về bưu điện để lấy thêm thư, trong trường hợp này quãng đường xe đi về bưu điện cũng bị tính vào tổng quãng đường đưa thư. Ngoài ra, thành phố Straightland là một thành phố thẳng, vì vậy ta có thể biểu diễn các địa điểm trong thành phố là các điểm trên trục số, và bưu điện là gốc trục số.

Để cho đề bài trở nên dễ hiểu, ta xét ví dụ sau: Giả sử sức chứa của xe đưa thư là ~100~ thư, và bưu điện cần chuyển ~50~ thư đến địa điểm ~-10, 175~ thư đến địa điểm ~10~ và ~20~ thư đến địa điểm ~25~. Hành trình đưa thư tối ưu là:

Đưa ~50~ thư đến địa điểm ~-10~, quay về bưu điện, đưa ~100~ thư đến địa điểm ~10~, quay về bưu điện, đưa ~75~ thư đến địa điểm ~10~, rồi đi tiếp đến địa điểm ~25~ để đưa ~20~, sau đó quay về bưu điện. Tổng quãng đường xe đưa thư cần đi là ~90~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~K (3 ≤ N ≤ 1000, 1 ≤ K ≤ 10000)~ lần lượt là số lượng địa điểm trong thành phố và số lượng thư mà xe đưa thư chứa được.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i~ và ~t_i~ lần lượt là vị trí của một địa điểm trong thành phố và số lượng thư cần chuyển đến vị trí đó. Dữ liệu vào đảm bảo ~−1500 ≤ x_1 < x_2 < ... < x_N~ và ~1 ≤ t_i ≤ 800~ với mọi ~i~. Không có địa điểm nào nằm ngay tại bưu điện.

Output

• Gồm một dòng chứa một số nguyên là tổng quãng đường đưa toàn bộ thư đến các địa điểm và quay trở về bưu điện.

Sample

Input #1

3 100
-10 50
10 175
25 20

Output #1

90

Input #2

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

Output #2

2668000

Problem source: Kc97ble - Free Contest 41