Max le texan – Épreuve régionale 2007

ENONCE

Max le texan est le meilleur homme canon de tout le Texas : la longueur de ses bonds surpasse celle de tous ses concurrents. Mais Max a un secret, il utilise un programme qui lui indique la meilleur trajectoire. A toi de faire comme lui pour tenter de l'égaler, en écrivant un programme donnant la longueur au sol maximale que peut parcourir Max avant de tomber.

La position de Max est repérée par les coordonnées (z,x) où z représente son altitude, et x son abscisse. Pour modifier sa trajectoire, Max peut agiter les bras, ce qui lui fait perdre 1 point d'energie, et Max peut récupérer 2 points d'energie en se raffraichissant dans un nuage. Max ne peut stocker qu'une quantité limitée d'énergie : si celle-ci dépasse 20 lorsque Max passe dans un nuage, elle est ramenée à 20. Sa vitesse est définie par un vecteur (vz,vx) (c'est-à-dire que si Max est au point (z,x) au temps t, il sera au point (z+vz, x+vx) au temps t+1). vx sera toujours égal à 1. vz vaut 1 si Max décide d'agiter les bras, et vaut -1 si Max décide de ne rien faire. La position initiale de Max est (0,0). Max commence avec E points d'énergie. (E est défini en entrée) Dans le ciel du Texas, il y a N nuages, repérés par leurs coordonnées (z(i),x(i)), 1\<=i\<=N. Pour se rafraichir dans un nuage, Max doit se trouver exactement à la position du nuage. Notez qu'à chaque pas de temps, Max commence par récupérer de l'energie s'il est sur un nuage, puis décide ou non d'agiter les bras ; ainsi, l'énergie récupérée est utilisable immédiatement. On dira que Max est tombé à l'abscisse x, s'il était à la position (0,x-1) au pas de temps précédent, et si Max a décidé de ne pas agiter les bras.

Ce schéma correspond à l'exemple 2. Les nuages sont dessinés en rouge, et une trajectoire optimale de Max est dessinée en bleu.

ENTREE

Sur la première ligne, un entier N, 0\<=N\<100000

Sur la deuxième ligne, un entier E, 0\<=E\<=20

Sur la troisième ligne, 2N entiers représentant les coordonnées (z(i),x(i)) des nuages : le 2*i-ième entier est l'altitude z du nuage i, et le (2i+1)-ième entier est l'abscisse x du nuage i. L'altitude des nuages est comprise entre 0 et 200, et l'abscisse des nuages est comprise entre 0 et 5000. Deux nuages ne peuvent avoir les mêmes coordonnées, et les nuages sont fournis en entrée par ordre des abscisses croissantes.

SORTIE

Un entier, la distance au sol maximale que Max peut parcourir, c'est-à-dire l'abscisse de sa chute.