Quỳnh đang tham gia một trò chơi bắn bóng bay tính điểm. Trên bầu trời có \(N\) quả bóng bay được đánh số từ \(1\) đến \(N\). Tại thời điểm bắt đầu trò chơi (\(t=0\)), quả bóng thứ \(i\) đang ở độ cao \(H_i\) và cứ sau mỗi giây, nó lại bay cao thêm \(S_i\) (đơn vị độ cao). Trò chơi diễn ra như sau:

• Tại thời điểm bắt đầu (\(t=0\)), Quỳnh bắn nổ một quả bóng bất kỳ.
• Sau đó, cứ mỗi giây trôi qua, tại các thời điểm \(t=1, t=2, \ldots, t=N-1\); Quỳnh lần lượt bắn nổ từng quả bóng.
• Trò chơi sẽ kết thúc vào thời điểm \(t=N-1\), khi Quỳnh đã bắn hết bóng.

Điểm chung cuộc của trò chơi lấy theo độ cao lớn nhất trong số \(N\) độ cao của các quả bóng tại thời điểm bị Quỳnh bắn nổ. Điểm càng thấp càng thể hiện "trình" bắn súng điêu luyện. Quỳnh sẽ chọn thứ tự bắn các quả bóng để đạt được điểm số thấp nhất.

Yêu cầu: Tìm điểm số chung cuộc nhỏ nhất có thể đạt được.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 10^5)\).
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(H_i, S_i\) \((1 \leq H_i, S_i \leq 10^9)\) mô tả độ cao ban đầu và tốc độ bay lên của quả bóng thứ \(i\).

Output

• Một số nguyên duy nhất là điểm số chung cuộc nhỏ nhất tìm được.

Example

4
12 4
5 6
21 2
14 7

23

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 8\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 300\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc thêm.