小 D 正在籌備一場環球旅行。出發前，他需要按計畫完成清單上的 $n$ 項物資準備操作，這些操作初始時按順序編號為 $1, 2, \dots, n$。

記當前的物資數量為整數 $x$，初始時 $x = 0$。第 $i$ 項操作由兩個正整數 $a_i, b_i$ 描述，執行該操作時會依次發生以下變化：

1. 先將 $x$ 增加 $a_i$（即令 $x \leftarrow x + a_i$）；
2. 隨後檢查 $x$ 的大小：若此時 $x > b_i$，則將 $x$ 削減至 $b_i$（即令 $x \leftarrow \min(x, b_i)$）。

在開始執行操作前，小 D 可以對清單順序進行至多一次調整：任選其中一項操作，將其取出並移至序列的末尾，其餘操作的相對順序保持不變（也可以選擇不進行任何調整）。

調整完畢後，小 D 將按新順序從前到後依次執行全部 $n$ 項操作，每項操作恰好執行一次。小 D 想知道，在所有操作執行完畢後，物資數量 $x$ 最大可能是多少？

輸入格式

從 stdin 中讀入資料。

第一行包含一個正整數 $n$，表示操作的數量。

接下來 $n$ 行，第 $i$ 行包含兩個正整數 $a_i, b_i$，描述第 $i$ 項操作的參數。

輸出格式

輸出到 stdout。

輸出一行一個整數，表示所有操作執行完畢後物資數量 $x$ 的最大可能值。

範例

輸入格式 1

3
1 100
100 90
1 1

輸出格式 1

90

說明

將第 $2$ 項操作移到序列末尾，操作執行順序變為 $1, 3, 2$。每項操作執行完畢後，$x$ 的值依次變為 $1, 1, 90$。

若將第 $1$ 項移到末尾，最終 $x = 2$；若不調整順序或將第 $3$ 項移到末尾，最終 $x = 1$。因此 $x$ 的最大可能值為 $90$。

範例 2

見選手目錄下的 supply/supply2.in 與 supply/supply2.ans。

該範例滿足測試點 $1 \sim 4$ 的約束條件。

範例 3

見選手目錄下的 supply/supply3.in 與 supply/supply3.ans。

該範例滿足測試點 $5 \sim 6$ 的約束條件。

範例 4

見選手目錄下的 supply/supply4.in 與 supply/supply4.ans。

該範例滿足測試點 $7 \sim 10$ 的約束條件。

資料範圍

對於全部資料，保證 $1 \le n \le 2 \times 10^5$，$1 \le a_i, b_i \le 10^9$。請注意：資料不保證 $a_i \le b_i$。

本題共有 $10$ 個測試點，每個測試點 $10$ 分，各測試點獨立計分。詳細資料範圍見下表。

特殊性質 A：$b_1 = b_2 = \dots = b_n$。