题目描述

A group of students has just finished their math lesson and they’re heading out for physical education. Their teacher has asked them to arrange themselves in a circle. After several minutes of busy moving around the court they have finally managed to position themselves so that they form a strictly convex polygon. They might not lie on the circle, but the teacher is happy to at least get some structure.

There is an even number of boys and an even number of girls in this group of $N$ students. They will practice ball passing in pairs, therefore the teacher has to pair them up. The teacher will pair boys among themselves and the same for girls.

The school administration has decided to address the decline in physical performance of their students. Therefore, they have implemented a quality measure for ball passing practice, which is the total distance traveled by the balls in a single round of ball passes between each pair. Help the teacher pair up the students in a way that will maximize this measure.

输入格式

The first line contains the number of students $N$. The second line contains a string $S$ of length $N$, which describes the students along the perimeter of the polygon with a character "B" for a boy and "G" for a girl. The following $N$ lines provide the locations of students with space-separated integer coordinates $X_i$ and $Y_i$ in the same order as they are described in the string $S$.

输出格式

Output the maximum ball passing distance that can be obtained by pairing up the students appropriately. The solution will be considered correct if the relative or absolute error compared to the official solution is within $10^{-6}$.

4
BGBG
0 0
0 1
1 1
1 0

2.828427125

4
GGBB
0 0
0 1
1 1
1 0

2

12
GBGBBGBBBBGB
0 -15
6 -14
19 -5
17 7
11 12
1 15
-9 13
-15 10
-17 8
-19 4
-16 -9
-13 -11

186.529031603

提示

Input limits

• $2 \leq N \leq 50$
• The number of boys and girls will both be even. Note that one of them can be zero.
• The coordinates $X_i$ and $Y_i$ won’t exceed 10 000 by absolute value.