Các đường phố của thành phố RightAngleles tạo thành một lưới ô vuông vô hạn. Hai đường bất kỳ hoặc song song hoặc vuông góc với nhau, và khoảng cách giữa hai đường song song gần nhau nhất bằng một đơn vị. Các đường chạy theo hướng tây–đông được gọi là đường ngang, đánh số bằng các số nguyên liên tiếp theo chiều từ nam lên bắc. Các đường chạy theo hướng nam–bắc được gọi là đường dọc, đánh số tương tự theo chiều từ tây sang đông.

Mỗi người dân sống trong một ngôi nhà có cửa ra vào tại một giao điểm của một đường ngang và một đường dọc. Nhiều người có thể sống trong cùng một ngôi nhà.

Thị trưởng muốn tăng sự ủng hộ của người dân bằng cách tổ chức bắn pháo hoa tại giao điểm của đường ngang chính, mang số \(0\), với một đường dọc nào đó. Vị trí nhà của tất cả những người muốn đến xem đã được biết trước. Pháo hoa có thể được quan sát dọc theo hai đường đi qua nơi bắn. Để bảo đảm an toàn, người xem phải đứng cách nơi bắn ít nhất \(S\) đơn vị.

Như vậy, nếu chọn đường dọc \(V\), mỗi người phải đi dọc các đường phố tới một giao điểm nằm trên đường ngang \(0\) hoặc đường dọc \(V\), cách giao điểm \((0,V)\) ít nhất \(S\) đơn vị. Chẳng hạn, khi \(S=2\), người xem có thể đứng tại mọi giao điểm trên đường ngang \(0\), trừ các giao điểm với đường dọc \(V-1,V,V+1\); tương tự, trên đường dọc \(V\) phải loại các giao điểm với đường ngang \(-1,0,1\).

Mức độ hài lòng của người dân phụ thuộc nhiều vào tổng quãng đường họ phải đi để xem pháo hoa. Hãy chọn vị trí bắn sao cho tổng quãng đường này nhỏ nhất và tính giá trị nhỏ nhất đó.

Dữ liệu vào

Dòng đầu chứa hai số nguyên dương \(N,S\), lần lượt là số người dân muốn xem pháo hoa và khoảng cách an toàn. Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(H_i,V_i\), là số hiệu đường ngang và đường dọc tại giao điểm có cửa nhà của người thứ \(i\).

Dữ liệu ra

In ra đúng một số nguyên: tổng quãng đường nhỏ nhất mà tất cả người dân phải đi để xem pháo hoa.

Ràng buộc

• \(1 \le N \le 10^5\).
• \(1 \le S \le 10^6\).
• \(-10^9 \le H_i,V_i \le 10^9\).

Phân nhóm

• Các bộ test có \(0 \le V_i \le 5000\) với mọi \(i\) chiếm \(20\) điểm.
• Các bộ test có \(N \le 5000\) chiếm tổng cộng \(40\) điểm.
• Toàn bộ các bộ test chiếm \(100\) điểm.

Ví dụ

7 2
3 -2
0 8
-4 8
-1 4
-2 13
-4 8
1 5

9