Alice promène tous les jours son vieux chien Bob dans son grand jardin. Malheureusement, avec l'âge, il va de plus en plus lentement et Alice n'a plus le temps. Elle souhaite laisser Bob faire sa promenade tout seul et décide de construire une clôture pour éviter que Bob ne quitte le jardin (il aime courir après la chienne du voisin). Elle souhaite profiter du fait que Bob suit tous les jours le même parcours pour réduire au minimum la quantité de clôture à acheter.

On vous donne la description du parcours de Bob, qui commence et se termine au même endroit (sa niche), sous la forme d'une succession de déplacements. Pour chaque déplacement, on indique la direction dans laquelle il se déplace, et la distance en mètres qu'il parcourt dans cette direction. Sachant que la clôture doit être constituée uniquement de segments parallèles aux axes Nord-Sud et Est-Ouest, et qu'Alice souhaite laisser au minimum un mètre entre le chien et la clôture, déterminer la longueur minimale de clôture qu'elle doit utiliser pour entourer entièrement le parcours de Bob.

• 2 <= N <= 10 000, où N est le nombre de déplacements du parcours de Bob,
• 1 <= L_i <= 100, où D est la longueur d'un déplacement de Bob.

La première ligne de l'entrée est constituée d'un entier N : le nombre de déplacements du parcours de Bob.

Chacune des N lignes suivantes décrit un déplacement du parcours de Bob. Chaque ligne est composée de deux entiers séparés par un espace : D_i, la direction du déplacement (0 pour Nord, 1 pour Est, 2 pour Sud, 3 pour Ouest), et L_i, la longueur du déplacement.

Vous devez écrire une ligne contenant un entier sur la sortie : la longueur minimale de clôture nécessaire pour contenir le parcours de Bob, en laissant toujours un mètre de distance au minimum entre le parcours et la clôture.

7
3 3
0 3
1 2
2 5
1 4
0 2
3 3

30

Le dessin ci-dessous correspond à l'exemple d'entrée. La niche est marquée d'un point noir, le chemin de Bob est représenté par les flèches et la clotûre en trait épais (bleu). Une grille en pointillés est représentée pour visualiser les distances. Exemple de code pour lire l'entrée en C/C++ :

#include <cstdio>


int main()
{
   int nbEtapes;
   scanf( "%d", &nbEtapes);

   // ....

   for(int etape = 0 ; etape < nbEtapes ; etape++)
   {
      int direction, distance;
      scanf("%d %d", &direction, &distance);
      // ....
   }
   printf("%d\n", votre solution);
   return 0;
}

Exemple de code pour lire l'entrée en OCaml :

let scan_int () = Scanf.scanf " %d" (fun x -> x)
let show_int n = Printf.printf "%d\n" n

let _ =
   let nbEtapes = scan_int() in

   (* ... *)

   for etape = 0 to nbEtapes - 1 do

      let direction = scan_int() in
      let distance = scan_int() in
      (* ... *)

   done;
   show_int (votre solution);

Deux conseils sont disponibles pour ce sujet. Utilisez-les si vous ne voyez pas comment le résoudre. Chaque conseil coûte 15 points.