Phỏng vấn

Bối cảnh

Một công ty tổ chức phỏng vấn xin việc cho \(N\) ứng viên. Mỗi ứng viên có một thời gian đến và một thời gian dự kiến cho cuộc phỏng vấn của mình. Chỉ một ứng viên có thể được phỏng vấn tại một thời điểm. Nếu nhiều ứng viên đến cùng một lúc, họ sẽ phải chờ đến lượt mình. Ví dụ, nếu một ứng viên đến vào thời điểm \(5\) và phỏng vấn mất \(7\) phút, một ứng viên khác đến vào thời điểm \(8\) sẽ phải chờ đến thời điểm \(12\) để bắt đầu phỏng vấn của mình.

Yêu cầu

Xác định thời điểm sớm nhất mà tất cả ứng viên có thể hoàn thành cuộc phỏng vấn.

Input

Dòng đầu tiên của đầu vào chứa \(N\) \((1\leq N \leq 100)\).

Mỗi dòng trong số \(N\) dòng tiếp theo mô tả một ứng viên, cho biết thời gian nó đến và thời gian cần thiết để hỏi; mỗi số này là số nguyên dương tối đa \(1,000,000\).

Output

Hãy xác định thời gian tối thiểu mà tất cả ứng viên có thể hoàn thành cuộc phỏng vấn.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

3
2 1
8 3
5 7

Output

15

Giải thích ví dụ

• Ứng viên 1 phỏng vấn xong lúc 3, ứng viên 3 bắt đầu lúc 5 và xong lúc 12, ứng viên 2 đợi đến 12 và kết thúc lúc 15.

Ở đây, ứng đầu tiên đến vào thời điểm \(2\) và được xử lý nhanh chóng. Cổng tạm thời trống rỗng cho đến khi con ứng viên thứ ba đến vào thời điểm \(5\) và bắt đầu được xử lý. Ứng viên thứ hai sau đó đến vào thời điểm \(8\) và phải chờ đến thời điểm \(5+7=12\) để bắt đầu trả lời câu hỏi, kết thúc vào thời điểm \(12+3 = 15\).

Thông tin học tập

• Buổi: B16
• Concepts: sorting, time-based simulation
• Giới hạn kiến thức: B01-B16
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 30