Chuyển phát hàng là công việc quan trọng trong thương mại điện tử, là lĩnh vực phát triển bùng nổ trong thời gian hiện nay. Ta xét công việc của một nhân viên giao hàng của Công ty XYZ chuyên bán hàng trên mạng. Nhân viên giao hàng cần phát những kiện hàng (được đóng gói trong các hộp cùng kích thước) đến các khách hàng có địa chỉ trên một đại lộ có dạng như một đường thẳng. Nhân viên giao hàng sẽ nhận các kiện hàng tại trụ sở công ty có tọa độ x = 0 và cần chuyển phát hàng đến n khách hàng được đánh số từ 1 đến n. Biết ~x_i~ và ~m_i~ là vị trí của khách hàng i và số lượng kiện hàng cần chuyển cho khách hàng này. Do các kiện hàng là khá cồng kềnh nên mỗi lần đi chuyển phát nhân viên giao hàng chỉ có thể mang theo không quá k kiện hàng. Nhân viên giao hàng xuất phát từ trụ sở, nhận một số (không quá k) kiện hàng và di chuyển theo đại lộ để chuyển phát cho một số khách hàng. Khi giao hết các kiện hàng mang theo, nhân viên giao hàng lại quay về trụ sở và lặp lại công việc nói trên cho đến khi chuyển phát được tất cả các kiện hàng cho khách hàng. Sau khi kết thúc công việc chuyển phát, nhân viên phải quay lại trụ sở công ty để nộp cho phòng kế toán tất cả các hóa đơn giao nhận có kí nhận của khách hàng. Giả thiết là: tốc độ di chuyển của nhân viên là 1 đơn vị khoảng cách trên một đơn vị thời gian. Thời gian nhận hàng ở trụ sở công ty và thời gian bàn giao hàng cho khách hàng được coi là bằng 0.

Yêu cầu:

Giả sử thời điểm mà nhân viên giao hàng bắt đầu công việc là 0. Hãy giúp nhân viên giao hàng tìm cách hoàn thành công việc đã mô tả ở trên tại thời điểm sớm nhất.

Dữ liệu:

• Dòng thứ nhất chứa hai số nguyên dương n và k (n ≤ ~10^3~; k ≤ ~10^7~).
• Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên ~x_i~ và ~m_i~ ( |~x_i~| ≤ ~10^7~; 1 ≤ ~m_i~ ≤ ~10^7~)

Các số ghi trên cùng một dòng cách nhau bởi dấu trống.

Kết quả:

Là một số nguyên là thời điểm sớm nhất mà người giao hàng có thể hoàn thành nhiệm vụ của mình.

Ví dụ:

INPUT 1

4 10
-7 5
-2 3
5 7
9 5

OUTPUT 1

42

INPUT 2

7 1
940000 10000000
950000 10000000
960000 10000000
970000 10000000
980000 10000000
990000 10000000
1000000 10000000

OUTPUT 2

1358000000000

Ràng buộc:

• Có 50% số test tương ứng 50% số điểm của bài có (1≤ n, k ≤ 100)
• Có 50% số test tương ứng 50% số điểm của bài có (100< n ≤ 100; 100< k ≤ ~10^7~)