DDR

Vasya plays Dance Dance Revolution. He must step on the arrows in the order they appear on screen, make no mistakes, and keep the total distance his feet travel as small as possible. The floor has five identical square pads. The center pad has no arrow. The other four pads lie on different sides of the center and are the left, right, up, and down arrows, written as L, R, U, and D. The layout is shown below. The song has N steps. Each step requires either one or two arrows pressed at the same time. Either foot can be placed on any of the five pads, regardless of where the other foot is, and both feet may share a pad. A foot can move from any position to any other position. Vasya starts with both feet on the center pad. At the end of the song, his feet can be anywhere. He must press every required arrow in order. He may place a foot on an arrow that is not required at that moment, and he may put one or both feet on the center pad at any time. To press an arrow, a foot must be at the center of that pad. Treat the feet as points. The center is (0, 0), the right pad is $(1, 0)$, the up pad is $(0, 1)$, the left pad is $(-1, 0)$, and the down pad is $(0, -1)$. Find the minimum total Euclidean distance the feet must travel during the song.

The first line contains one integer N (1 ≤ N ≤ 100,000), the number of steps. Each of the next N lines starts with k_i (k_i is 1 or 2), the number of arrows to press at that step. Then come k_i distinct characters from L, R, U, D, separated by a space when k_i is 2.

Print one real number, the minimum total distance. The answer is accepted if its absolute or relative error does not exceed $10^{-9}$.

In the first sample, Vasya moves his left foot to the down pad and his right foot to the up pad, and presses the first two arrows. Then he moves both feet diagonally to the left and right pads. The total distance is $1 + 1 + \sqrt{2} + \sqrt{2} \approx 4.8284271247$. In the second sample, one foot goes to the up pad, which costs distance 1.