Il piccolo D sta preparando un viaggio intorno al mondo. Prima della partenza, deve completare come previsto le $n$ operazioni di preparazione delle provviste presenti sulla sua lista; tali operazioni sono inizialmente numerate in ordine da $1, 2, \dots, n$.

Indichiamo la quantità attuale di provviste con l'intero $x$, dove inizialmente $x = 0$. La $i$-esima operazione è descritta da due interi positivi $a_i, b_i$; quando viene eseguita tale operazione si verificano nell'ordine le seguenti modifiche:

1. Prima si aumenta $x$ di $a_i$ (ossia si pone $x \leftarrow x + a_i$);
2. Successivamente si controlla il valore di $x$: se in quel momento $x > b_i$, allora si riduce $x$ a $b_i$ (ossia si pone $x \leftarrow \min(x, b_i)$).

Prima di iniziare a eseguire le operazioni, il piccolo D può effettuare al massimo una modifica all'ordine della lista: scegliere una qualsiasi operazione, rimuoverla e spostarla alla fine della sequenza, lasciando invariato l'ordine relativo delle restanti operazioni (può anche scegliere di non effettuare alcuna modifica).

Terminata la modifica, il piccolo D eseguirà tutte le $n$ operazioni in sequenza dall'inizio alla fine secondo il nuovo ordine, eseguendo ciascuna operazione esattamente una volta. Il piccolo D vuole sapere: una volta completate tutte le operazioni, qual è il valore massimo possibile della quantità di provviste $x$?

Ingresso

Leggere i dati da stdin.

La prima riga contiene un intero positivo $n$, che rappresenta il numero di operazioni.

Nelle successive $n$ righe, la $i$-esima riga contiene due interi positivi $a_i, b_i$, che descrivono i parametri della $i$-esima operazione.

Uscita

Scrivere su stdout.

Stampare una sola riga contenente un intero, che rappresenta il valore massimo possibile della quantità di provviste $x$ dopo l'esecuzione di tutte le operazioni.

Esempi

Ingresso 1

3
1 100
100 90
1 1

Uscita 1

90

Nota

Spostando la $2$-a operazione alla fine della sequenza, l'ordine di esecuzione delle operazioni diventa $1, 3, 2$. Al termine di ciascuna operazione, il valore di $x$ diventa rispettivamente $1, 1, 90$.

Se si sposta la $1$-a operazione alla fine, alla fine si ottiene $x = 2$; se non si modifica l'ordine oppure si sposta la $3$-a operazione alla fine, alla fine si ottiene $x = 1$. Pertanto, il valore massimo possibile di $x$ è $90$.

Esempio 2

Si vedano supply/supply2.in e supply/supply2.ans nella directory del concorrente.

Questo esempio soddisfa i vincoli dei casi di prova $1 \sim 4$.

Esempio 3

Si vedano supply/supply3.in e supply/supply3.ans nella directory del concorrente.

Questo esempio soddisfa i vincoli dei casi di prova $5 \sim 6$.

Esempio 4

Si vedano supply/supply4.in e supply/supply4.ans nella directory del concorrente.

Questo esempio soddisfa i vincoli dei casi di prova $7 \sim 10$.

Vincoli

Per tutti i dati, è garantito che $1 \le n \le 2 \times 10^5$ e $1 \le a_i, b_i \le 10^9$. Si noti che: i dati non garantiscono $a_i \le b_i$.

Questo problema prevede in totale $10$ casi di prova, ciascuno del valore di $10$ punti, valutati in modo indipendente. I limiti dettagliati sono riportati nella tabella seguente.

Proprietà speciale A: $b_1 = b_2 = \dots = b_n$.