Prologin, le concours national d'informatique

Énoncé¶

Contre toute attente, vous avez été sélectionné en épreuve régionale Prologin (surréaliste, n'est-ce pas ?). Après avoir passé l'épreuve écrite et dégusté de délicieuses pizzas Tortue Ninja, il est maintenant temps d'aborder l'épreuve machine.

Il y a deux exercices par niveau, le 1^er et le 2^d. Dans le cadre de cet exercice, réussir l'exercice n°1 du niveau i débloque l'exercice n°1 du niveau i + 1 (et résoudre l'exercice n°2 débloque l'exercice n°2). En cas de blocage, au bout de 15 minutes, l'accès à l'autre exercice de même niveau vous est débloqué.

Sachant que vous commencez avec les deux exercices de niveau 1 débloqués (mais non résolus), combien de temps vous faut-il au minimum pour réussir un exercice du dernier niveau ?

Entrée¶

Sur la première ligne, le nombre N de niveaux.
Sur les N lignes suivantes, deux nombres, respectivement le nombre de minutes requises pour résoudre l'exercice 1 et 2.

Sortie¶

Le temps minimal pour réussir un exercice du dernier niveau.

Contraintes¶

1 <= N <= 100 000

Contraintes d'exécution

Utilisation mémoire maximum: 4200 kilo-octets
Temps d'exécution maximum: 2000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée

Exemple de sortie

Commentaire

Pour arriver à l'exercice 3 le plus rapidement possible, il faut faire l'exercice 1 de niveau 1 (en 15 minutes), puis attendre 15 minutes au niveau 2 pour débloquer (et faire) l'exercice 2 (15 minutes) et enfin faire l'exercice 2 de niveau 3 (30 minutes). Cela nécessite, au total, 15+15+15+30=75 minutes.