Tại một nhà ga, có một hàng người đang chờ mua vé. Người thứ đến ga tại thời điểm và cần thời gian để mua vé. Nhà ga có một quầy bán vé duy nhất. Quầy vé này chỉ phục vụ theo từng đợt. Mỗi đợt, quầy vé có thể phục vụ một nhóm không quá người và chỉ những người đã có mặt tại ga trước hoặc bằng thời điểm quầy bắt đầu phục vụ đợt đó. Thời gian bắt đầu phục vụ một đợt bằng thời gian kết thúc của đợt trước đó, hoặc thời điểm đến của người đầu tiên được phục vụ trong đợt (nếu quầy đang rảnh). Thời gian để phục vụ một nhóm bằng tổng thời gian phục vụ của từng người trong nhóm đó.
Yêu cầu: Hãy tìm thời gian mà người cuối cùng trong người mua xong vé.
Dữ liệu:
Dòng đầu chứa hai số nguyên .
dòng tiếp theo, dòng thứ chứa hai số nguyên và .
Kết quả: Một số nguyên duy nhất là thời điểm người cuối cùng mua xong vé.
Ví dụ:
Dữ liệu:
4 2
0 5
1 5
2 5
3 5
Kết quả:
20
Giải thích:
Đây là một cách. Cách tối ưu:
Đợt 1: Bắt đầu lúc , phục vụ người đầu tiên. Thời gian phục vụ 5. Kết thúc lúc 5.
Đợt 2: Bắt đầu lúc , phục vụ người thứ hai và ba. Thời gian phục vụ . Kết thúc lúc .
Đợt 3: Bắt đầu lúc , phục vụ người cuối cùng. Thời gian phục vụ 5. Kết thúc lúc .
