Tại trạm rửa xe tự động có N cột nước được đánh số từ 1 tới N và một máy làm khô xe. Mỗi xe đến rửa phải đến một cột nước không có xe đang rửa để làm sạch xe và sau đó đến máy làm khô xe. Thời gian di chuyển đến cột nước và đến máy làm khô xe không đáng kể nên có thể bỏ qua. trạm rửa xe bắt đầu làm việc từ thời điểm 0. có M khách hàng đến rửa xe đánh số từ 1 đến M. Mỗi khách hàng thứ k (1<=k<=M) đến rửa xe vào thời điểm t_k , làm sạch xe ở cột nước hết a_k đơn vị thời gian và làm khô xe hết b_k đơn vị thời gian. Các khách hàng được đánh số thứ tự theo chiều tăng của thời điểm đến rửa xe. Hai khách hàng đến rửa xe cùng một thời điểm thì khách hàng có số thứ tự nhỏ hơn sẽ được phục vụ trước.

Yêu cầu: xác định thời điểm hoàn thành quá trình rửa xe sớm nhất của mỗi khách hàng.

Ví dụ: có N=2 cột nước, M=4 khách hàng đến rửa xe vào các thời điểm tương ứng là 1,1,2,2; làm sạch xe hết thời gian tương ứng là 3,2,2,1 và thời gian làm khô xe tương ứng là 3,2,1,4. Khi đó khách hàng thứ 2 rửa xe xong ở thời điểm 1+2+2 = 5, khách hàng thứ 1 rửa xe xong vào thời điểm 5+3 =8; khách hàng thứ 3 rửa xe xong vào thời điểm 8+1=9; khách hàng thứ 4 rửa xe xong vào thời điểm 9+4=13.