POSTMAN - Postman
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Chuyền phát hàng là một 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 các 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 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 ở vị trí 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 ximi 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 trở 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 trở 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ểmm 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 đầu tiên chứa hai số nguyên dưong được ghi cách nhau bởi dấu cách nk (n < 1000; < 107).
• Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên được ghi cách nhau bởi dấu cách xi (I
xiI < 107) và mi (1 < mi < 107).

Ket quả:

Ghi ra 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

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

Output

42

Input

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

Output

1358000000000000


Nguồn: NĐN 20172018

Back to Top