题目描述

一座城市中有若干路口，路口之间由街道连接。每条街道都是连接两个路口的直线段，且从任意路口出发，沿街道都能到达其他所有路口。

城市中的一个点可以是路口，也可以是某条街道内部的任意一点。两个点之间的步行距离，是只允许沿街道行走时两点间最短路线的长度；一条街道的长度等于其两个端点之间的欧氏距离。

街道在路口以外即使在平面投影上相交，也不视为连通；可以认为这些位置使用了隧道或立交桥。

给定所有路口的坐标和街道连接关系，请求出城市中任意两点之间步行距离的最大值。注意，取得最大值的点不一定是路口，也可能位于街道内部。

输入格式

第一行一个整数 $n$，表示路口数量。

第二行包含 $n$ 个整数 $x_0,x_1,\ldots,x_{n-1}$，表示各路口的横坐标。

第三行包含 $n$ 个整数 $y_0,y_1,\ldots,y_{n-1}$，表示各路口的纵坐标。

接下来 $n$ 行，每行一个长度为 $n$ 的字符串 streets[i]。若 streets[i][j] 为 Y，则路口 $i$ 与路口 $j$ 之间有一条街道；若为 N，则没有。

输出格式

输出一个实数，表示任意两点之间步行距离的最大值。

当你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$ 时，视为正确。

样例 1

2
0 1
0 1
NY
YN

1.4142135623730951

只有两个路口，答案就是连接它们的街道长度 $\sqrt 2$。

样例 2

4
0 2 2 0
0 0 2 2
NNYY
NNYY
YYNN
YYNN

4.82842712474619

取得最大步行距离的两个点在平面中的坐标都是 $(1,1)$，但它们位于两条不同的街道上，因此并不连通。

样例 3

4
0 1 1 0
0 0 1 1
NYNY
YNYN
NYNY
YNYN

2.0

样例 4

4
-1000 -1000 1000 1000
-1000 1000 1000 -1000
NYNY
YNYN
NYNY
YNYN

4000.0

样例 5

4
0 1 2 2
0 0 1 -1
NYNN
YNYY
NYNY
NYYN

3.414213562373095

样例 6

3
0 1 0
0 0 1
NYY
YNY
YYN

1.7071067811865475

三个路口构成一个等腰直角三角形。一组最优点为 $(0,0)$ 和 $(\tfrac12,\tfrac12)$。

数据范围与保证

• $2\le n\le 50$；
• $-1000\le x_i,y_i\le 1000$；
• 所有路口的坐标两两不同；
• streets[i] 的长度均为 $n$，且只包含 N 和 Y；
• streets[i][i] 始终为 N；
• 对任意 $i,j$，均有 streets[i][j] = streets[j][i]；
• 任意两个路口之间都存在一条沿街道行走的路径。