En vieillissant, Farmer John devient grincheux et paranoïaque. Oubliant comment la diversité bovine a fait prospérer sa ferme durant des années, il bâtit une immense clôture, décourage les visites voisines et interdit totalement l’entrée depuis quelques fermes. Les vaches sont contrariées : plus de visites aux amies, et annulation de l’Olympiade internationale de traite attendue toute l’année.

Même les voisines autorisées peinent : porte unique, questions intenses pour chacune, souvent longue file.

Pour $N$ visiteuses, heure d’arrivée et durée des questions sont données. Une seule interrogée à la fois, arrivées proches attendent une par une. Arrivée5, durée7 : celle arrivée8 attend12.

Trouvez le plus tôt où toutes peuvent entrer.

Entrée

Première ligne $N$, entier positif au plus100. Puis $N$ lignes arrivée et durée, chaque entier positif au plus1,000,000.

Sortie

Temps minimal où toutes sont traitées.

Exemples

Entrée 1

3
2 1
8 3
5 7

Sortie 1

15

Remarque

Première arrive2, vite traitée ; porte libre jusqu’à troisième arrivée5. Deuxième arrive8, attend $5+7=12$, finit $12+3 = 15$.

Auteur du problème : Brian Dean