ZADANIE

Rozważmy niepuste drzewo binarne T etykietowane liczbami całkowitymi i zapisane wierzchołkowo tak, że pozycję dowolnego wierzchołka x w drzewie T określa ciąg skierowań krawędzi (L - lewa krawędź, R - prawa krawędź) jakie pokonamy przechodząc w tym drzewie ścieżkę od korzenia do wierzchołka x.



Wyznacz kolejno minimalną oraz maksymalną możliwą sumę etykiet wierzchołków rozważanego drzewa występujących na dowolnej ścieżce wierzchołek zewnętrzny (liść) drzewa T - korzeń drzewa T.



WEJŚCIE

Ciąg wierszy zakończony symbolem znaku końca pliku (EOF) reprezentujący poprawnie (zgodnie z powyższym opisem) pewne drzewo binarne T. Każdy pojedynczy wiersz zakończony znakiem nowej linii (kod ASCII 10) opisujący pozycję wierzchołka w drzewie T i zawierający:

 - liczba całkowita - etykieta wierzchołka,

 - znak odstępu  (kod ASCII 32),

 - ciąg znaków L (kod ASCII 76) oraz R (kod ASCII 82) - ciąg skierowań krawędzi na ścieżce od korzenia drzewa do rozważanego wierzchołka.



WYJŚCIE

Wiersz zawierający dwie liczby całkowite będące rozwiązaniem postawionego problemu oddzielone znakiem odstępu.



OGRANICZENIA

Liczba wierzchołków drzewa T nie większa niż 10^7. Wartości etykiety wierzchołków drzewa ograniczone odpowiednio przez -10^9 oraz 10^9. Wysokość h drzewa T ograniczona przez 2^6.



LIMITY

Złożoność czasowa O(hn), złożoność pamięciowa O(n), gdzie n jest liczbą wierzchołków drzewa T a h jest jego wysokością.



PRZYKŁAD 1

wejście:

3 LL

5

-8 R

1 L

-2 LR

wyjście:

-3 9


/*

KOMENTARZ DO ROZWIĄZANIA


Konstrukcja drzewa binarnego:


    5

   / \

  1  -8

 / \

3  -2


Możliwe sumy etykiet wierzchołków na ścieżce liść drzewa – korzeń drzewa to kolejno 3+1+5=9, (-2)+1+5=4 oraz (-8)+5=-3. Wartości minimalna i maksymalna w/w sum to -3 i 9.

*/



PRZYKŁAD 2

wejście:

8 L

-5 LL

8 LLR

-8 LRR

2 LR

-9 LLL

-3 LRL

6 RR

2

-8 R

wyjście:

-4 13



PRZYKŁAD 3

wejście:

-82 LRL

80 L

-63

-92 LRLR

-63 RLRL

51 RR

-95 RRLR

67 RRRLR

-73 RLLL

29 RLR

-49 RRL

-27 RLL

73 LR

39 RRRL

-42 RL

-29 LL

-25 RLRR

-77 RLLR

-88 LLR

4 RRR

3 RRLLR

-64 RRLL

-80 R

-85 LLRR

38 LLL

wyjście:

-289 26