\(N\) cô bò của FJ đã quyết định đi nghỉ và, thật kỳ diệu, tìm được một hãng hàng không sẵn lòng bán vé cho chúng. Tuy nhiên, khi đến sân bay và bắt đầu lên máy bay, chúng phải đối mặt với một vấn đề thú vị.

Máy bay có \(N\) ghế, được mô hình hóa thành các điểm từ \(x=1\) đến \(x=N\) trên trục số. Cả \(N\) cô bò (\(1 \le N \le 200\,000\)) đang xếp hàng chờ đi đến ghế của mình. Bò \(N\) ở vị trí \(x=0\), bò \(N-1\) ở vị trí \(x=-1\), và cứ tiếp tục như vậy. Bò \(i\) được xếp vào ghế \(S_i\), trong đó \(S_1,\ldots,S_N\) là một hoán vị của \(1,\ldots,N\).

Ở mỗi bước thời gian, mỗi cô bò bước sang phải nếu có thể. Khi bò \(i\) đến ghế \(S_i\) của mình, cô sẽ dừng lại để cất hành lý vào ngăn phía trên; việc này mất \(T_i\) giây, sau đó cô mới ngồi xuống. Trong \(T_i\) bước ấy, cô bò đứng ngay sau (nếu có) bị chặn và không thể tiến lên. Nếu phía sau cô là cả một hàng bò thì toàn bộ hàng đó cũng bị chặn.

Hỏi cần bao lâu để tất cả các cô bò ngồi xuống?

Tổng \(T_i\) của tất cả các cô bò nhỏ hơn \(1\,000\,000\,000\).

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(S_i\) và \(T_i\) cách nhau bởi dấu cách.

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(S_1,\ldots,S_N\) là một hoán vị của \(1,\ldots,N\).
• Tổng \(T_i\) của tất cả các cô bò nhỏ hơn \(1\,000\,000\,000\).

Dữ liệu ra

In ra thời gian cần thiết để tất cả các cô bò ngồi vào ghế.

Ví dụ

3
2 5
3 10
1 5

19

cows -> 123
           123 <- seats

 123
   123

 12
   123

    12
   123

Nguồn

USACO 2014 February Contest, Gold — Airplane Boarding

Tác giả: Travis Hance.