Rozważmy wielokąt $P$ o poziomych i pionowych bokach oraz $N$ wierzchołkach. Boki mogą stykać się tylko końcami, a w każdym wierzchołku spotykają się końce dokładnie dwóch boków. Idąc wzdłuż boków $P$ przeciwnie do ruchu wskazówek zegara, w każdym wierzchołku skręcamy w lewo lub w prawo. Oznaczmy skręt w lewo przez $L$, a w prawo przez $R$. Wtedy napis złożony z $L$ i $R$ opisuje wielokąt. Na przykład wielokąt z rysunku 1 opisuje napis

$LLRLLRRLLRLLRLLRRLLR$

Opisując wielokąt napisem, zawsze zaczynamy od górnego końca jego najbardziej lewego boku. Ten znak to zawsze $L$.

Rysunki 1 i 2

Wielokąt opisany podanym napisem musi spełniać następujący warunek: dla dowolnej pionowej prostej $V$ istnieją co najwyżej dwa punkty przecięcia $V$ z wnętrzami poziomych boków wielokąta (bez ich końców).

Dla wielokąta $P$ niech $B(P)$ oznacza najmniejszy prostokąt o poziomych i pionowych bokach zawierający $P$. Wyznaczają go pionowe i poziome proste pokrywające się z najbardziej lewym, prawym, górnym i dolnym bokiem $P$ (rysunek 2).

Dla danego napisu długości $N$, złożonego z $L$ i $R$, rysujemy opisany nim wielokąt $P$ spełniający powyższy warunek. Każdy bok $P$ musi mieć długość całkowitą. Napisz program minimalizujący pole $B(P)$ i wypisujący to minimum.

Należy zaimplementować następującą funkcję dla programu oceniającego.

int polygon(string S);

Funkcja przyjmuje napis $S$ długości $N$, którego każdy znak to $L$ lub $R$. Wśród wielokątów $P$ opisanych przez $S$ należy znaleźć taki, który minimalizuje pole $B(P)$, i zwrócić to pole.

Szczegóły implementacji

Prześlij dokładnie jeden plik o nazwie polygon.c lub polygon.cpp. Musi on implementować następującą funkcję.

int polygon(string S);

Funkcja musi działać zgodnie z powyższym opisem. Można tworzyć inne funkcje do użytku wewnętrznego. Przesłany kod nie może wykonywać operacji wejścia/wyjścia ani uzyskiwać dostępu do innych plików.

Przykładowy program oceniający

Udostępniony program oceniający czyta wejście w następującym formacie.

• Wiersz 1: $N$ (długość napisu).

• Wiersz 2: napis $c_1c_2\cdots c_N$ długości $N$ ($c_1=L$ oraz $c_i=L$ lub $R$ dla $2\le i\le N$).

Udostępniony program oceniający wypisuje wartość zwróconą przez polygon.

Ograniczenia

• Napis wejściowy składa się z $L$ i $R$.

• Zawsze istnieje co najmniej jeden wielokąt opisany napisem wejściowym, który spełnia powyższe warunki.

• $4 \le N \le 800$.

Podzadania

1 (20 punktów)

• $N \le 10$.

2 (36 punktów)

• $N \le 40$.

3 (21 punktów)

• $N \le 100$.

4 (73 punktów)

• Brak dodatkowych ograniczeń.

Przykład

Wejście 1

8
LLLRRLLL

Wyjście 1

6

Wejście 2

20
LLRLLRRLLRLLRLLRRLLR

Wyjście 2

15