MétaPrologin – Regional event 2013

Level 5

É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 1er et le 2e. 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

Runtime constraints

Maximum memory usage
4200 kilobytes
Maximum execution time
2000 milliseconds

Input/output samples

Sample input
3
15 35
35 15
30 30
Sample output
75
Note

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.

Sample input
5
15 45
30 25
15 45
60 15
30 30
Sample output
120
Note

Il faudra attendre que l'autre exercice se débloque aux niveaux 4. Il faudra donc 15+30+15+15+15+30=120 minutes pour arriver au dernier niveau.

Submit your solution

You have to register or log in to be able to submit your solution.