Castle Design

문제

The ICPC kingdom has decided to build a new castle. The boundary of the castle is designed as a rectilinear polygon with edges parallel to the $xx$-axis or to the $yy$-axis. To minimize the damage exposed by the enemy attack, the kingdom wants to minimize the perimeter of the rectilinear polygon. Let us go into more detail.

A rectilinear polygon $PP$ of $nn$ vertices with integer coordinates realizes a turn sequence $SS$ of length $nn$ of two letters L and R if there is a counterclockwise traverse along the boundary of $PP$ such that the turns at vertices of $PP$, encountered during the traverse, form the turn sequence $SS$; the left turn at a convex vertex corresponds to L and the right turn at a reflex vertex corresponds to R. For example, the rectilinear polygon in Figure B.1(a) realizes the turn sequence $S=S\; =$ RLLRLLLRRLLRLRLL of length $1616$. Another turn sequence $S=S\; =$ LLRLLRLLRLRLLR of length $1414$ can be realized by rectilinear polygons in Figure B.1(b) and B.1(c). Note that a turn sequence can have infinitely many realizations of rectilinear polygons in the integral plane.

A polygon is simple if there are no two edges that intersect except at the end vertices of adjacent edges. A polygon is monotone to an axis if its intersection with a line orthogonal to the axis is at most one segment. The monotone polygon is called $22$-monotone if it is monotone to both $xx$-axis and the $yy$-axis, and $11$-monotone if it is monotone to the one axis but not to the other axis. For example, the polygon in Figure B.1(a) is $11$-monotone because it is monotone to only one axis, the $xx$-axis, while the polygons in Figure B.1(b) and B.1(c) are $22$-monotone. A turn sequence is also said to be $tt$-monotone if any simple rectilinear polygon realizing the turn sequence is $tt$-monotone where $𝑡=1,2𝑡\; =\; 1,\; 2$.

Figure B.1 (a) A simple $11$-monotone rectilinear polygon realizing an $11$-monotone turn sequence RLLRLLLRRLLRLRLL (starting from the marked vertex). (b) A simple $22$-monotone rectilinear polygon realizing a $22$-monotone turn sequence LLRLLRLLRLRLLR (starting from the marked vertex). (c) The $22$-monotone rectilinear polygon with the minimum perimeter for the turn sequence in (b).

The perimeter of a rectilinear polygon is the sum of the length of its edges. The perimeter of the polygon in Figure B.1(b) is $1818$, but this is not minimum for LLRLLRLLRLRLLR. Its minimum perimeter should be $1616$ as in Figure B.1(c).

Given a 𝑡𝑡-monotone turn sequence of $nn$ turns for $t=1,2t\; =\; 1,\; 2$, write a program to compute the minimum perimeter of simple $tt$-monotone rectilinear polygons that realize the input $tt$-monotone turn sequence.

입력

Your program is to read from standard input. The input is one line containing a string of $nn$ turns of two uppercase letters L and R that is a $tt$-monotone turn sequence, where $t=1,2t\; =\; 1,\; 2$ and 4 ≤ n ≤ 10^{t+3}.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the positive integer that is the minimum perimeter of simple $tt$-monotone rectilinear polygons that realize the input $tt$-monotone turn sequence for $t=1,2t\; =\; 1,\; 2$.

LLRLLRLLRLRLLR

16

RLLRLLLRRLLRLRLL

20

LLRRLLLLRRLL

16

RLLRLLRLLRLL

12