EIU Programming Practices and Exams

Trong môi trường đa nhiệm, có thể xảy ra tình huống nhiều tiến trình đồng thời sẵn sàng để xử lý. Mục tiêu của các hệ phân chia thời gian (time-sharing) là chuyển đổi CPU qua lại giữa các tiến trình một cách thường xuyên để nhiều người sử dụng có thể tương tác cùng lúc với từng chương trình trong quá trình xử lý.

Để thực hiện được mục tiêu này, hệ điều hành phải lựa chọn tiến trình được xử lý tiếp theo. Bộ điều phối sẽ sử dụng một giải thuật điều phối thích hợp để thực hiện nhiệm vụ này. Thuật toán thời gian còn lại ngắn nhất (SRTF) là một trong những thuật toán có thể được sử dụng. Khi có một tiến trình mới được thêm vào hoặc CPU rãnh, bộ điều phối sẽ chọn tiến trình có thời gian thực hiện còn lại ngắn nhất để tiếp tục xử lý. Cho các tiến trình với thời điểm được thêm vào và thời gian chạy, hãy tìm thời điểm mà các tiến trình được xử lý xong. Tiến trình A đuơc thêm vào thời điểm t thì cũng có thể được chọn vào thời điểm t và tiến trình A được chọn vào thời điểm t thì sẽ bắt đầu xử lý từ thời điểm t.

Input

Dòng đầu tiên là số tiến trình (n ≤ 10⁵).

n dòng tiếp theo, mỗi dòng là một tiến trình gồm thời điểm được thêm vào t và thời gian cần để hoàn thành l (t, l ≤ 10⁹).

Output

Một số nguyên duy nhất là thời điểm các tiến trình được thực hiện xong.

Example

Input:
5
0 10
5 10
11 8
40 5
11 2

Output:
44