turnuri

Într-un laborator cibernetic se fac experimente cu roboți. Pe o bandă de lucru se află așezate unul lângă altul, $N$ cuburi galbene și albastre, numeroate în ordine cu valori de la $1$ la $N$. Pentru fiecare cub se cunoaște latura acestuia, exprimată în centimetri, și culoarea, codificată prin simbolul $g$ (pentru galben) sau $a$ (pentru albastru).

Un robot inteligent este programat să construiască turnuri prin așezarea cuburilor unul peste altul. El se află în fața benzii de lucru, analizează fiecare cub în ordine, de la primul la ultimul, și procedează astfel:

• dacă este primul cub, îl lasă la locul lui pe bandă;
• așază cubul numerotat cu $K$ peste cubul numerotat cu $K-1$ doar dacă el are culoarea diferită și latura mai mică decât cubul $K-1$. Această operație se efectuează în cazul în care cubul $K-1$ se află deja într-un turn construit anterior sau dacă el a rămas în poziția inițială. În cazul în care cubul $K$ nu poate fi așezat peste cubul $K-1$, el rămâne la locul lui.

Cerință

Știind că un turn poate fi format din cel puțin un cub, scrieți un program care să determine:

1. numărul final $T$ al turnurilor de pe bandă și $H$, înălțimea celui mai înalt turn care se poate forma, exprimată în centimetri;
2. cel mai mare număr de cuburi Nmax ce pot forma un turn, dacă cele $N$ cuburi ar putea fi rearanjate inițial pe bandă, unul lângă altul.

Date de intrare

Fișierul de intrare turnuri.in conține:

• pe prima linie un număr natural $C$ care reprezintă numărul cerinței și poate fi $1$ sau $2$.
• pe cea de-a doua linie un număr natural $N$ ce reprezintă numărul cuburilor de pe bandă;
• pe fiecare dintre următoarele $N$ linii, câte un număr natural care reprezintă latura unui cub, urmat de un spațiu și simbolul $g$ sau $a$, pentru codificarea culorii cubului.

Date de ieșire

În fișierul de ieșire turnuri.out va conține pentru cerința $1$ pe prima linie două valori, separate printr-un spațiu, ce reprezintă $T$ și $H$. Pentru cerința $2$ fișierul va conține pe prima linie numărul $Nmax$.

Restricții și precizări

• $1 \leq N \leq 10 \ 000$ și $1 \leq$ latura unui cub $\leq 500 \ 000$;
• nu există două cuburi cu laturi egale;
• se acordă $10$ puncte din oficiu. Pentru rezolvarea corectă a primei cerințe se acordă $30$ de puncte, pentru rezolvarea corectă a celei de-a doua cerințe se acordă $60$ de puncte.

Exemplul 1

turnuri.in

1
6
18 a
13 g
15 a
10 a
8 g
2 a

turnuri.out

3 31

Explicație

Se va rezolva cerința $1$. Al doilea cub se așază peste primul și formează un turn cu înălțimea de $31$ de centimetri. Al treilea cub formează singur un turn cu înălțimea $15$ centimetri. Ultimele trei cuburi formează un turn cu înălțimea $20$ de centimetri. Numărul turnurilor este $3$. Înălțimea celui mai înalt turn este de $31$ de centimetri.

Exemplul 2

turnuri.in

2
6
18 a
13 g
15 a
10 a
8 g
2 a

turnuri.out

5

Explicație

Se va rezolva cerința $2$. O posibilă rearanjare a cuburilor ar fi următoarea:

Primele $5$ cuburi formează un turn.