arche_perdue

Indiana Jones, après des années de recherche à la bibliothèque, a enfin trouvé l'Arche perdue ! Malheureusement, après un périple de plusieurs milliers de kilomètres, 42 énnemis tués, 17 crocodiles mangés, un ravin le sépare encore de cette Arche dont il doit ensuite rapporter le contenu avec lui. Pour traverser ce ravin, il y a un pont, ou du moins ce qu'il en reste ! Sur ce pont il ne reste que peu de planches de bois pour poser ses pieds, certaines semblent à vu d'oeil assez solides, alors que d'autres ne pourront visiblement être utilisées qu'une fois dans l'aller-retour (grande acuité visuelle d'Indiana Jones). Plus un saut est grand plus il est fatiguant et donc dangereux, pour cette raison Indiana Jones souhaite calculer l'itinéraire de planche en planche de façon à minimiser le plus grand saut à effectuer lors de l'aller-retour.

Entrée : La première ligne de l'entrée est un entier < 100 qui indique le nombre de ravins à franchir de cette façon (oui, parce que Indiana Jones est souvent confronté à ce problème). Chaque instance de ravin commence par une ligne contenant deux entiers 0 ≤ N ≤ 100 et 1 ≤ D ≤ 1000000000, où N est le nombre de planches de bois et D la distance entre les deux côtés du ravin. Les N lignes suivantes décrivent chaque planche de bois. Dans une description de planche on trouve deux informations. Tout d'abord, une lettre "B", qui signifie qu'il s'agit d'une planche solide que l'on pourra utiliser à plusieurs reprises, ou "S", qui à l'inverse est une planche sur laquelle on ne pourra s'appuyer qu'une fois. Cette lettre est ensuite suivie d'un tiret "-" et d'un entier 0 ≤ M ≤ D indiquant la distance entre le départ et la planche. Les planches sont indiquées par ordre croissant de M.

Sortie : La sortie indique le numéro du cas traité et sa solution, à savoir la minimisation du plus grand saut à effectuer (voir l'exemple).

Input

3
1 10
B-5
1 10
S-5
2 10
B-3
S-6

Télécharger l'entrée

Output

Case 1: 5
Case 2: 10
Case 3: 7

Télécharger la sortie