Klein D bereitet eine Weltreise vor. Vor der Abreise muss er planmäßig die $n$ Operationen zur Vorbereitung der Vorräte auf seiner Liste abschließen, die anfangs der Reihe nach mit $1, 2, \dots, n$ nummeriert sind.

Sei die aktuelle Menge an Vorräten die ganze Zahl $x$, wobei anfangs $x = 0$ gilt. Die $i$-te Operation wird durch zwei positive ganze Zahlen $a_i, b_i$ beschrieben; bei der Ausführung dieser Operation treten nacheinander die folgenden Änderungen ein:

1. Zuerst wird $x$ um $a_i$ erhöht (d. h. es wird $x \leftarrow x + a_i$ gesetzt);
2. Anschließend wird die Größe von $x$ überprüft: Falls zu diesem Zeitpunkt $x > b_i$ gilt, wird $x$ auf $b_i$ verringert (d. h. es wird $x \leftarrow \min(x, b_i)$ gesetzt).

Bevor er mit der Ausführung der Operationen beginnt, darf Klein D höchstens eine Anpassung an der Reihenfolge der Liste vornehmen: Er wählt eine beliebige Operation aus, entnimmt sie und verschiebt sie an das Ende der Folge, während die relative Reihenfolge der übrigen Operationen unverändert bleibt (er kann sich auch dafür entscheiden, gar keine Anpassung vorzunehmen).

Nach Abschluss der Anpassung führt Klein D alle $n$ Operationen in der neuen Reihenfolge von vorne nach hinten nacheinander aus, wobei jede Operation genau einmal ausgeführt wird. Klein D möchte wissen, wie groß die Menge an Vorräten $x$ nach Abschluss aller Operationen höchstens sein kann.

Eingabe

Die Daten werden von stdin eingelesen.

Die erste Zeile enthält eine positive ganze Zahl $n$, die die Anzahl der Operationen angibt.

In den folgenden $n$ Zeilen enthält die $i$-te Zeile zwei positive ganze Zahlen $a_i, b_i$, die die Parameter der $i$-ten Operation beschreiben.

Ausgabe

Die Ausgabe erfolgt auf stdout.

Gib eine Zeile mit einer einzigen ganzen Zahl aus, die den größtmöglichen Wert der Vorratsmenge $x$ nach Ausführung aller Operationen angibt.

Beispiele

Eingabe 1

3
1 100
100 90
1 1

Ausgabe 1

90

Hinweis

Verschiebt man die $2$-te Operation an das Ende der Folge, so wird die Ausführungsreihenfolge der Operationen zu $1, 3, 2$. Nach Ausführung jeder Operation nimmt $x$ nacheinander die Werte $1, 1, 90$ an.

Verschiebt man die $1$-te Operation an das Ende, gilt am Ende $x = 2$; lässt man die Reihenfolge unverändert oder verschiebt man die $3$-te Operation an das Ende, gilt am Ende $x = 1$. Daher beträgt der größtmögliche Wert von $x$ genau $90$.

Beispiel 2

Siehe supply/supply2.in und supply/supply2.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Bedingungen der Testfälle $1 \sim 4$.

Beispiel 3

Siehe supply/supply3.in und supply/supply3.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Bedingungen der Testfälle $5 \sim 6$.

Beispiel 4

Siehe supply/supply4.in und supply/supply4.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Bedingungen der Testfälle $7 \sim 10$.

Beschränkungen

Für alle Daten ist $1 \le n \le 2 \times 10^5$ und $1 \le a_i, b_i \le 10^9$ garantiert. Bitte beachten Sie: Die Daten garantieren nicht, dass $a_i \le b_i$ gilt.

Diese Aufgabe umfasst insgesamt $10$ Testfälle zu je $10$ Punkten, wobei jeder Testfall unabhängig gewertet wird. Die genauen Datenbereiche sind in der folgenden Tabelle angegeben.

Spezielle Eigenschaft A: $b_1 = b_2 = \dots = b_n$.