URI Online Judge | 1913

Help Mr. Barriga

By Jadson José Monteiro Oliveira, Faculdade de Balsas BR Brazil

Timelimit: 1

Nhonho, son of Mr. Barriga is participating of a new game created by the townhouse’s children, the game is well know by “cylinders Tower”. The game is to build the tallest tower made up of cylinders, respecting all the rules, of course! Just below it is described the operation of the game.

Tired of seeing his son complain of losing forever and consequently to hear the phrase "Look at him huh! Look at him huh! Look at him ... " multiple times, Mr. Barriga want to give a small tip for Nhonho, telling the height greater than can be built given the list with the characteristics of cylinders available for construction of the tower. However, although being good at math and collect the rent properly, Mr. Barriga was unable to calculate the maximum height that the tower may have due to the large amount of available cylinders. So he hired you to write a program able to inform this value.

To help you better understand the problem, Mr. Barriga showed him through a drawing the height of the highest possible tower to be built with five parts, following all the rules of the game. Below you can see the drawing of Mr. Barriga.

torre_cilindro.png

Input

The input contains several test cases. The first line of each test case contains an integer N (1 ≤ N ≤ 10³), representing the number of cylinders arranged on the table, following N rows, each row having a height h (1 ≤ h ≤ 1000) of the cylinder in centimeters, the radius r (1 ≤ r ≤ 1000) of the cylinder base and a word p, representing the color of the cylinder. The word can be: VERMELHO (red in portuguese), LARANJA (orange in portuguese), VERDE (green in portuguese), or AZUL (blue in portuguese). The end of input is indicated as N == 0, which should not be processed.

Output

For each test case, your program should print a single line with the value the height of the largest cylinders tower that can be built, followed by the word "centimetro(s)” (centimeters in portuguese).

Input Sample Output Sample

5

5 3 VERMELHO

4 2 LARANJA

1 1 VERDE

3 5 LARANJA

2 4 AZUL

3

10 10 LARANJA

5 10 VERDE

6 5 VERMELHO

0

15 centimetro(s)

11 centimetro(s)