Petit D prépare un voyage autour du monde. Avant son départ, il doit accomplir comme prévu les $n$ opérations de préparation des provisions figurant sur sa liste, ces opérations étant initialement numérotées dans l'ordre $1, 2, \dots, n$.

Notons $x$ l'entier représentant la quantité actuelle de provisions, avec initialement $x = 0$. La $i$-ème opération est décrite par deux entiers strictement positifs $a_i, b_i$. Lors de l'exécution de cette opération, les changements suivants se produisent successivement :

1. On augmente d'abord $x$ de $a_i$ (c'est-à-dire que l'on affecte $x \leftarrow x + a_i$) ;
2. On vérifie ensuite la valeur de $x$ : si à ce moment $x > b_i$, alors on réduit $x$ à $b_i$ (c'est-à-dire que l'on affecte $x \leftarrow \min(x, b_i)$).

Avant de commencer à exécuter les opérations, Petit D peut effectuer au plus un ajustement de l'ordre de la liste : choisir arbitrairement l'une des opérations, la retirer et la déplacer à la fin de la séquence, tandis que l'ordre relatif des autres opérations reste inchangé (il peut aussi choisir de ne faire aucun ajustement).

Une fois l'ajustement terminé, Petit D exécutera successivement la totalité des $n$ opérations du début à la fin selon le nouvel ordre, chaque opération étant exécutée exactement une fois. Petit D aimerait savoir quelle est la valeur maximale possible de la quantité de provisions $x$ une fois toutes les opérations exécutées.

Entrée

Lire les données depuis stdin.

La première ligne contient un entier strictement positif $n$, représentant le nombre d'opérations.

Les $n$ lignes suivantes contiennent chacune, sur la $i$-ème ligne, deux entiers strictement positifs $a_i, b_i$ décrivant les paramètres de la $i$-ème opération.

Sortie

Écrire sur stdout.

Afficher sur une seule ligne un entier représentant la valeur maximale possible de la quantité de provisions $x$ après l'exécution de toutes les opérations.

Exemples

Entrée 1

3
1 100
100 90
1 1

Sortie 1

90

Remarque

En déplaçant la $2$-ème opération à la fin de la séquence, l'ordre d'exécution des opérations devient $1, 3, 2$. Après l'exécution de chaque opération, la valeur de $x$ devient successivement $1, 1, 90$.

Si l'on déplace la $1$-ère opération à la fin, on obtient finalement $x = 2$ ; si l'on ne modifie pas l'ordre ou si l'on déplace la $3$-ème opération à la fin, on obtient finalement $x = 1$. Par conséquent, la valeur maximale possible de $x$ est $90$.

Exemple 2

Voir supply/supply2.in et supply/supply2.ans dans le répertoire du candidat.

Cet exemple satisfait les contraintes des tests $1 \sim 4$.

Exemple 3

Voir supply/supply3.in et supply/supply3.ans dans le répertoire du candidat.

Cet exemple satisfait les contraintes des tests $5 \sim 6$.

Exemple 4

Voir supply/supply4.in et supply/supply4.ans dans le répertoire du candidat.

Cet exemple satisfait les contraintes des tests $7 \sim 10$.

Contraintes

Pour l'ensemble des données, il est garanti que $1 \le n \le 2 \times 10^5$ et $1 \le a_i, b_i \le 10^9$. Veuillez noter : les données ne garantissent pas que $a_i \le b_i$.

Ce problème comporte au total $10$ tests, valant chacun $10$ points, et chaque test est évalué indépendamment. Les contraintes détaillées figurent dans le tableau ci-dessous.

Propriété spéciale A : $b_1 = b_2 = \dots = b_n$.