Tiểu D đang chuẩn bị cho một chuyến du lịch vòng quanh thế giới. Trước khi khởi hành, anh ấy cần hoàn thành $n$ thao tác chuẩn bị vật tư trong danh sách theo kế hoạch, các thao tác này ban đầu được đánh số thứ tự là $1, 2, \dots, n$.

Gọi số lượng vật tư hiện tại là số nguyên $x$, ban đầu $x = 0$. Thao tác thứ $i$ được mô tả bởi hai số nguyên dương $a_i, b_i$, khi thực hiện thao tác này sẽ lần lượt xảy ra các thay đổi sau:

1. Trước tiên tăng $x$ thêm $a_i$ (tức là gán $x \leftarrow x + a_i$);
2. Tiếp theo kiểm tra độ lớn của $x$: nếu lúc này $x > b_i$ thì giảm $x$ xuống còn $b_i$ (tức là gán $x \leftarrow \min(x, b_i)$).

Trước khi bắt đầu thực hiện các thao tác, Tiểu D có thể thực hiện nhiều nhất một lần điều chỉnh đối với thứ tự danh sách: chọn tùy ý một thao tác trong đó, lấy nó ra và chuyển xuống cuối dãy, thứ tự tương đối của các thao tác còn lại giữ nguyên không đổi (cũng có thể chọn không thực hiện bất kỳ điều chỉnh nào).

Sau khi điều chỉnh xong, Tiểu D sẽ lần lượt thực hiện toàn bộ $n$ thao tác từ trước ra sau theo thứ tự mới, mỗi thao tác được thực hiện đúng một lần. Tiểu D muốn biết, sau khi tất cả các thao tác được thực hiện xong, số lượng vật tư $x$ lớn nhất có thể là bao nhiêu?

Dữ liệu vào

Đọc dữ liệu từ stdin.

Dòng đầu tiên chứa một số nguyên dương $n$, biểu thị số lượng thao tác.

Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên dương $a_i, b_i$, mô tả các tham số của thao tác thứ $i$.

Dữ liệu ra

Ghi ra stdout.

In ra một dòng gồm một số nguyên, biểu thị giá trị lớn nhất có thể của số lượng vật tư $x$ sau khi tất cả các thao tác được thực hiện xong.

Ví dụ

Dữ liệu vào 1

3
1 100
100 90
1 1

Dữ liệu ra 1

90

Ghi chú

Chuyển thao tác thứ $2$ xuống cuối dãy, thứ tự thực hiện thao tác trở thành $1, 3, 2$. Sau khi mỗi thao tác được thực hiện xong, giá trị của $x$ lần lượt trở thành $1, 1, 90$.

Nếu chuyển thao tác thứ $1$ xuống cuối, cuối cùng $x = 2$; nếu không điều chỉnh thứ tự hoặc chuyển thao tác thứ $3$ xuống cuối, cuối cùng $x = 1$. Do đó giá trị lớn nhất có thể của $x$ là $90$.

Ví dụ 2

Xem supply/supply2.in và supply/supply2.ans trong thư mục của thí sinh.

Ví dụ này thỏa mãn điều kiện ràng buộc của các test $1 \sim 4$.

Ví dụ 3

Xem supply/supply3.in và supply/supply3.ans trong thư mục của thí sinh.

Ví dụ này thỏa mãn điều kiện ràng buộc của các test $5 \sim 6$.

Ví dụ 4

Xem supply/supply4.in và supply/supply4.ans trong thư mục của thí sinh.

Ví dụ này thỏa mãn điều kiện ràng buộc của các test $7 \sim 10$.

Giới hạn

Đối với toàn bộ dữ liệu, đảm bảo $1 \le n \le 2 \times 10^5$, $1 \le a_i, b_i \le 10^9$. Xin lưu ý: dữ liệu không đảm bảo $a_i \le b_i$.

Bài toán này có tổng cộng $10$ test, mỗi test $10$ điểm, các test được chấm điểm độc lập. Phạm vi dữ liệu chi tiết xem bảng dưới đây.

Tính chất đặc biệt A: $b_1 = b_2 = \dots = b_n$.