D Kecil sedang mempersiapkan perjalanan keliling dunia. Sebelum berangkat, ia perlu menyelesaikan $n$ operasi persiapan logistik pada daftar sesuai rencana, yang pada awalnya diberi nomor $1, 2, \dots, n$ secara berurutan.

Misalkan jumlah logistik saat ini adalah bilangan bulat $x$, dengan nilai awal $x = 0$. Operasi ke-$i$ dijelaskan oleh dua bilangan bulat positif $a_i, b_i$. Saat menjalankan operasi tersebut, perubahan berikut akan terjadi secara berurutan:

1. Pertama, tambahkan $x$ sebesar $a_i$ (yaitu menetapkan $x \leftarrow x + a_i$);
2. Kemudian periksa nilai $x$: jika saat ini $x > b_i$, maka kurangi $x$ menjadi $b_i$ (yaitu menetapkan $x \leftarrow \min(x, b_i)$).

Sebelum mulai menjalankan operasi, D Kecil dapat melakukan paling banyak satu kali penyesuaian terhadap urutan daftar: memilih salah satu operasi secara bebas, mengambilnya lalu memindahkannya ke akhir barisan, sementara urutan relatif dari operasi lainnya tetap tidak berubah (ia juga dapat memilih untuk tidak melakukan penyesuaian apa pun).

Setelah penyesuaian selesai, D Kecil akan menjalankan seluruh $n$ operasi secara berurutan dari depan ke belakang sesuai urutan baru, dengan setiap operasi dijalankan tepat satu kali. D Kecil ingin tahu, setelah semua operasi selesai dijalankan, berapa jumlah logistik $x$ maksimum yang mungkin?

Masukan

Baca data dari stdin.

Baris pertama berisi sebuah bilangan bulat positif $n$, yang menyatakan jumlah operasi.

Selanjutnya terdapat $n$ baris, baris ke-$i$ berisi dua bilangan bulat positif $a_i, b_i$, yang menjelaskan parameter dari operasi ke-$i$.

Keluaran

Keluarkan ke stdout.

Keluarkan satu baris berisi satu bilangan bulat, yang menyatakan nilai maksimum yang mungkin dari jumlah logistik $x$ setelah semua operasi selesai dijalankan.

Contoh

Masukan 1

3
1 100
100 90
1 1

Keluaran 1

90

Catatan

Pindahkan operasi ke-$2$ ke akhir barisan, sehingga urutan pelaksanaan operasi menjadi $1, 3, 2$. Setelah setiap operasi selesai dijalankan, nilai $x$ secara berurutan menjadi $1, 1, 90$.

Jika operasi ke-$1$ dipindahkan ke akhir, nilai akhirnya adalah $x = 2$; jika urutan tidak disesuaikan atau operasi ke-$3$ dipindahkan ke akhir, nilai akhirnya adalah $x = 1$. Oleh karena itu, nilai maksimum yang mungkin dari $x$ adalah $90$.

Contoh 2

Lihat supply/supply2.in dan supply/supply2.ans di direktori peserta.

Contoh ini memenuhi batasan kasus uji $1 \sim 4$.

Contoh 3

Lihat supply/supply3.in dan supply/supply3.ans di direktori peserta.

Contoh ini memenuhi batasan kasus uji $5 \sim 6$.

Contoh 4

Lihat supply/supply4.in dan supply/supply4.ans di direktori peserta.

Contoh ini memenuhi batasan kasus uji $7 \sim 10$.

Batasan

Untuk seluruh data, dijamin bahwa $1 \le n \le 2 \times 10^5$ dan $1 \le a_i, b_i \le 10^9$. Perhatikan bahwa: data tidak menjamin $a_i \le b_i$.

Soal ini memiliki total $10$ kasus uji, masing-masing bernilai $10$ poin, dan setiap kasus uji dinilai secara independen. Batasan data secara rinci dapat dilihat pada tabel di bawah ini.

Sifat Khusus A: $b_1 = b_2 = \dots = b_n$.