Consider a polygon $P$ consisting of horizontal and vertical edges and $N$ vertices. The edges of polygon $P$ can only meet at their endpoints, and exactly two edges meet at each vertex. When moving along the edges of the polygon in a counter-clockwise direction, one turns either left or right at each vertex. Let us represent a left turn at a vertex as $L$ and a right turn as $R$. Then, a string consisting of $L$ and $R$ represents the polygon. For example, the polygon in Figure 1 is represented by the string $LLRLLRRLLRLLRLLRRLLR$. When representing a polygon with a string, the start of the string is always the top vertex of the leftmost edge of the polygon. It can be seen that this character is always $L$.

Figure 1

Figure 2

The polygon represented by the given string must satisfy the following condition: for any vertical line $V$, $V$ has at most 2 intersection points with the interior of the horizontal edges of the polygon (excluding the endpoints). For a polygon $P$, let $B(P)$ denote the smallest rectangle with vertical and horizontal edges that contains $P$. It can be seen that this is determined by the vertical and horizontal lines that overlap with the leftmost, rightmost, top, and bottom edges of $P$ (Figure 2).

Given a string of length $N$ consisting of characters $L$ and $R$, draw a polygon $P$ that satisfies the above conditions represented by this string. At this time, the length of each edge of $P$ must be an integer. Write a program that minimizes the area of $B(P)$ and outputs the minimum value. You must implement the following function for the administrator:

• int polygon(string S): Receives a string $S$ of length $N$ as an argument. Here, each character of the string $S$ is $L$ or $R$. This function finds the polygon $P$ represented by $S$ that minimizes the area of $B(P)$ and returns that area.

Implementation Details

You must submit exactly one file named polygon.c or polygon.cpp. This file must implement the following function:

int polygon(string S);

This function must operate as described above. Of course, you may create other functions to use internally. The submitted code must not perform input/output or access other files.

Constraints

• The input string consists of characters $L$ or $R$.
• There is always at least one polygon that satisfies the above conditions represented by the input string.
• $4 \le N \le 800$.

Subtasks

• Subtask 1 [20 points]: $N \le 10$.
• Subtask 2 [36 points]: $N \le 40$.
• Subtask 3 [21 points]: $N \le 100$.
• Subtask 4 [73 points]: No additional constraints.

Examples

Input 1

8
LLLRRLLL

Output 1

6

Input 2

20
LLRLLRRLLRLLRLLRRLLR

Output 2

15