Prologin, the French National Computer Science Contest

Énoncé¶

Des tetriminos (pièces du jeu Tetris) arrivent vers vous (de gauche à droite), vous devez les détruire dans leur ordre d'arrivée. Ceux-ci sont décomposables en deux lignes de blocs, celle du haut et celle du bas. Tirer sur un tetrimino lui retire un bloc, dès qu'une des deux lignes du tetrimino est détruite, le tetrimino disparaît.

À chaque tour, vous pouvez :

tirer pour détruire le bloc de tetrimino le plus proche sur votre ligne ;
utiliser les touches directionnelles (haut ou bas) pour changer de ligne.

Sachant que vous commencez sur la case du haut, sur combien de touches devrez-vous appuyer au minimum pour détruire tous les blocs ?

Entrée¶

Sur la première ligne, le nombre N de tetriminos.
Sur les N prochaines lignes : un tetrimino, c'est-à-dire deux nombres, le premier est le nombre de blocs de la ligne du haut, le second est le nombre de blocs de la ligne du bas.

Les N dernières lignes sont dans l'ordre d'arrivée des tetriminos, la dernière ligne contient donc le dernier tetrimino à détruire.

Sortie¶

Le nombre de touches nécessaires pour détruire tous les blocs.

Contraintes¶

1 <= N <= 100 000

Runtime constraints

Maximum memory usage: 5000 kilobytes
Maximum execution time: 2000 milliseconds

Input/output samples

Sample input

Sample output

Note

Pour détruire le premier tetrimino (1,3), il faut tirer une fois, puis aller en bas et tirer une fois pour détruire le deuxième (3,1) et enfin tirer deux fois pour détruire le troisième tetrimino (2,2). Ce qui fait un total de 5 tours (1 tir + 1 déplacement + 1 tir + 2 tirs).