Hàng Đợi Gói Tin CSKH MobiFone

Mô tả

Trung tâm chăm sóc khách hàng MobiFone tiếp nhận yêu cầu hỗ trợ qua một máy chủ xử lý theo cơ chế FIFO (vào trước — ra trước). Mỗi ngày, khách hàng gọi đến liên tục và hệ thống xếp từng gói tin vào hàng đợi. Khi máy chủ rảnh, nó lấy gói tin đứng đầu hàng đợi ra và xử lý trong đúng số mili giây mà gói tin đó yêu cầu. Trong lúc máy chủ đang xử lý một gói tin, các gói tin mới đến vẫn tiếp tục xếp hàng chờ.

Bạn là kỹ sư vận hành, cần xác định thời điểm máy chủ hoàn tất xử lý toàn bộ chuỗi gói tin trong ngày để lên lịch bảo trì.

Quy trình cụ thể như sau:

• Gói tin thứ nhất đến đúng lúc t = 0, được xử lý ngay lập tức.
• Gói tin thứ i (từ 1) đến vào thời điểm a[i-1] (mili giây tính từ đầu ngày), cần d[i-1] mili giây để xử lý xong.
• Máy chủ chỉ xử lý một gói tin tại một thời điểm. Gói tin nào đến trước và phải chờ thì sẽ được lấy ra xử lý ngay khi máy chủ rảnh.

Hãy tính thời điểm (t tổng cộng, tính bằng mili giây) mà gói tin cuối cùng hoàn tất xử lý.

Đầu vào

• Số nguyên n — số lượng gói tin trong ngày.
• Mảng a gồm n số nguyên dương — thời điểm đến của từng gói tin, theo thứ tự xếp hàng.
• Mảng d gồm n số nguyên dương — thời lượng xử lý của từng gói tin tương ứng.

Đầu ra

• Trả về một số nguyên duy nhất — thời điểm hoàn tất gói tin cuối cùng.

Ràng buộc

• 1 ≤ n ≤ 10^5
• 0 ≤ a[i] ≤ 10^9
• 1 ≤ d[i] ≤ 10^9
• Các gói tin được cho theo thứ tự thời gian đến không giảm: a[0] ≤ a[1] ≤ ... ≤ a[n-1].

Ví dụ

Ví dụ 1:

• Đầu vào: n = 3, a = [0, 2, 5], d = [4, 3, 2]
• Đầu ra: 9

Giải thích từng bước:

1. t = 0: Gói tin 0 đến, máy chủ rảnh → xử lý ngay. Kết thúc lúc 0 + 4 = 4.
2. t = 2: Gói tin 1 đến, máy chủ đang bận → xếp hàng chờ.
3. t = 4: Gói tin 0 xong, máy chủ lấy gói tin 1 ra xử lý. Kết thúc lúc 4 + 3 = 7.
4. t = 5: Gói tin 2 đến, máy chủ đang bận → xếp hàng chờ.
5. t = 7: Gói tin 1 xong, máy chủ lấy gói tin 2 ra xử lý. Kết thúc lúc 7 + 2 = 9.

Gói tin cuối cùng hoàn tất lúc t = 9.