시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB31121142.308%

문제

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 $x$-axis or to the $y$-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 $P$ of $n$ vertices with integer coordinates realizes a turn sequence $S$ of length $n$ of two letters L and R if there is a counterclockwise traverse along the boundary of $P$ such that the turns at vertices of $P$, encountered during the traverse, form the turn sequence $S$; 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 =$ RLLRLLLRRLLRLRLL of length $16$. Another turn sequence $S =$ LLRLLRLLRLRLLR of length $14$ 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 $2$-monotone if it is monotone to both $x$-axis and the $y$-axis, and $1$-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 $1$-monotone because it is monotone to only one axis, the $x$-axis, while the polygons in Figure B.1(b) and B.1(c) are $2$-monotone. A turn sequence is also said to be $t$-monotone if any simple rectilinear polygon realizing the turn sequence is $t$-monotone where $𝑡 = 1, 2$.

Figure B.1 (a) A simple $1$-monotone rectilinear polygon realizing an $1$-monotone turn sequence RLLRLLLRRLLRLRLL (starting from the marked vertex). (b) A simple $2$-monotone rectilinear polygon realizing a $2$-monotone turn sequence LLRLLRLLRLRLLR (starting from the marked vertex). (c) The $2$-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 $18$, but this is not minimum for LLRLLRLLRLRLLR. Its minimum perimeter should be $16$ as in Figure B.1(c).

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

입력

Your program is to read from standard input. The input is one line containing a string of $n$ turns of two uppercase letters L and R that is a $t$-monotone turn sequence, where $t = 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 $t$-monotone rectilinear polygons that realize the input $t$-monotone turn sequence for $t = 1, 2$.

예제 입력 1

LLRLLRLLRLRLLR

예제 출력 1

16

예제 입력 2

RLLRLLLRRLLRLRLL

예제 출력 2

20

예제 입력 3

LLRRLLLLRRLL

예제 출력 3

16

예제 입력 4

RLLRLLRLLRLL

예제 출력 4

12