CROSSCOWI - Ghé thăm trang trại
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ớ: 128 megabyte
Đăng bởi: admin

Thật không may cho bác nông dân John, do già nua mà bác ngày càng trở nên nhăn nhó và hoang tưởng. Bỏ qua những đóng góp của những con bò hàng xóm trong việc giúp nông trại của bác mọc cỏ tươi tốt trong nhiều năm qua, mới đây bác quyết định xây dựng một hàng rào vĩ đại xung quanh nông trại của bác, ngăn cản những chú bò từ các nông trại hàng xóm tới thăm, và nghiêm cấm hoàn toàn những nông trại còn lại. Những cô bò rất hoang mang bởi sự việc đó, không chỉ bởi vì họ không còn được tới thăm những người bạn của họ mà còn bởi vì nó sẽ là nguyên nhân để họ hủy tư cách tham gia cuộc thi vắt Sữa Bò Quốc Tế, một sự kiện mà những cô bò mong mỏi chờ đợi hàng năm.

Những cô bò hàng xóm, những cô mà còn có khả năng vào nông trại bác John, nhận thấy là con đường cũng rất gian khó, chúng chỉ được vào nông trại thông qua một cánh cổng duy nhất nơi mà mỗi cô bò là đối tượng để đặt ra những câu hỏi quá quắt, thường là nguyên nhân của việc tắc nghẽn, tạo ra một hàng dài các cô bò.

Với mỗi cô bò trong N cô bò viếng thăm nông trại, bạn sẽ được biết thời điểm mà cô tới cánh cổng và thời gian cần thiết để cô trả lời hết những câu hỏi quá quắt. Chỉ có một cô bò bị hỏi và trả lời tại một thời điểm nên nếu nhiều cô bò tới cánh cổng gần sát nhau, các cô phải đợi đến lượt từng người một. Cho ví dụ như có một cô bò tới cánh cổng tại thời điểm 5 và mất 7 đơn vị thời gian để trả lời các câu hỏi, như vậy nếu một cô bò khác tới cánh cổng tại thời điểm 8 thì phải đợi cho tới thời điểm 12 rồi mới được bắt đầu trả lời câu hỏi.

Bạn hãy xác định thời điểm sớm nhất để tất cả các cô bò có thể vào nông trại.

Dữ liệu vào:

- Dòng đầu chứa N (1 ≤ N ≤ 100).

- N dòng tiếp theo, mỗi dòng miêu tả một cô bò: thời gian tới cánh cổng và thời gian cần thiết để trả lời câu hỏi; mỗi số là một số nguyên dương nhiều nhất là 106.

Kết quả ra:

- Hãy xác định thời điểm sớm nhất mà tất cả các cô bò có thể hoàn thành các câu trả lời và có thể đi vào nông trại.

Ví dụ

  • input
    3
    2 1
    8 3
    5 7
    output
    15
Back to Top