vase

Specialiştii chimişti au reuşit crearea în laborator a unei game diversificate de substanţe lichide nemiscibile (care nu se amestecă între ele), de aceeaşi densitate şi de culori diferite.

Acest rezultat a fost utilizat de către specialiştii fizicieni pentru studiul principiului vaselor comunicante. Conform acestui principiu „într-un sistem de vase comunicante nivelul lichidului este acelaşi, indiferent de forma vaselor”.

Experimentele fizicienilor se desfăşoară astfel:

Într-un sistem cu două vase comunicante, gradat identic pe fiecare ramură cu $0$, $1$, $2$, $3$, $\dots$, fizicienii introduc un număr de $n$ lichide, pe ramura din stânga sau pe ramura din dreapta. Volumele introduse din fiecare lichid, notate cu $V_i$ ($1 \leq i \leq n$), sunt numere naturale nenule pare astfel încât, la echilibru, orice lichid se va aşeza între două gradaţii de aceeaşi parte a unei ramuri sau pe cele două ramuri ale sistemului de vase comunicante. Lichidele sunt identificate prin intermediul culorii acestora, culori numerotate cu $1$, $2$, $3$, $\dots$, $n$. Introducerea lichidelor în sistemul cu două vase comunicante se face în ordinea crescătoare a numerelor culorilor, începând cu lichidul de culoare $1$.

Scopul experimentului este de a determina gradaţia maximă la care se ridică lichidele în sistemul cu două vase comunicante, precum şi între ce gradaţii se găseşte un lichid de culoare $x$, dintre cele introduse.

De exemplu, dacă în sistemul cu două vase comunicante se introduc $n=3$ lichide în ordinea: $V_1=4$ lichid de culoare $1$ introdus prin ramura din dreapta (operaţie codificată 4 D), $V_2=4$ lichid de culoare $2$ introdus prin ramura din stânga (operaţie codificată 4 S) şi $V_3=2$ lichid de culoare $3$ introdus prin ramura din stânga (operaţie codificată 2 S) atunci gradaţia maximă la care se ridică nivelul lichidelor în sistemul cu două vase comunicante este $5$, iar lichidul de culoare $x=2$ se găseşte între gradaţiile: $3$ pe ramura din stânga (3 S) şi $1$ pe ramura din dreapta (1 D), conform figurii alăturate.

Cerinţă

Să se scrie un program care cunoscând numărul $n$ de lichide introduse în sistemul cu două vase comunicante, volumul $V_i$ şi ramura prin care se face introducerea lichidului de culoare $i$ ($1 \leq i \leq n$), precum şi culoarea $x$, să calculeze gradaţia maximă la care se ridică lichidele în acest sistem la echilibru şi între ce gradaţii se găseşte lichidul de culoare $x$.

Date de intrare

Prima linie a fişierului de intrare vase.in conţine un singur număr natural nenul $n$, cu semnificaţia de mai sus. Fiecare linie, din următoarele $n$, conţine câte două valori separate printr-un spaţiu: un număr natural nenul par şi o literă mare, S sau D, reprezentând volumul introdus din lichidul de culoare $i$, respectiv ramura (S pentru ramura din stânga şi D pentru ramura din dreapta) prin care se face introducerea acestuia. Linia $n+2$ a fişierului de intrare conţine un singur număr nenul $x$ ce reprezintă culoarea lichidului căutat.

Date de ieşire

Fişierul de ieşire vase.out va conţine pe prima linie un număr natural nenul ce reprezintă gradaţia maximă la care se ridică lichidele în sistemul de vase comunicante la echilibru. Următoarele două linii vor conţine fiecare câte două valori separate printr-un spaţiu: un număr natural şi o literă mare (S sau D), reprezentând gradaţia şi ramura între care se aşează lichidul căutat.

Restricţii şi precizări

• $1 \leq x \leq n \leq 100\ 000$
• $2 \leq V_i \leq 100\ 000$ pentru $1 \leq i \leq n$
• Sistemul de vase este gradat în aceleaşi unităţi de măsură în care sunt exprimate volumele de lichid.
• Dacă lichidul căutat, de culoare $x$, se aşează pe aceeaşi ramură se va afişa întâi gradaţia superioară şi apoi cea inferioară.
• Dacă lichidul căutat, de culoare $x$, se aşează pe ramuri diferite se va afişa întâi gradaţia de pe ramura din stânga şi apoi cea de pe ramura din dreapta.
• Dacă una dintre gradaţiile între care se situează lichidul căutat, de culoare $x$, este $0$ atunci se consideră că aceasta gradaţie se găseşte pe aceeaşi ramură cu cealaltă gradaţie.
• Pentru rezolvarea primei cerinţe se acordă $20\%$ din punctaj, iar pentru a doua cerinţă $80\%$ din punctaj.

Exemplu

vase.in

3
4 D
4 S
2 S
2

vase.out

5
3 S
1 D

Explicație

Se introduc $3$ lichide în sistemul de două vase comunicante:

• primul cu volumul $4$, se introduce prin dreapta şi are culoarea $1$;
• al doilea cu volumul $4$, se introduce prin stânga şi are culoarea $2$;
• al treilea cu volumul $2$, se introduce prin stânga şi are culoarea $3$;

Se caută gradaţiile ce corespund lichidului de culoare $2$.
Gradaţia maximă la care ajunge nivelul lichidului este $5$.
Lichidul de culoare $2$ se aşează între gradaţiile $3$ pe ramura din stânga şi $1$ pe ramura din dreapta.