Description

你在上了大学之后结交了一群志同道合的朋友们，大家约好将来都在厦门工作，房子也买在厦门
但是好巧不巧，20年后你们一群人分别在厦门和台湾工作，一部分人在厦门，一部分人在台湾
老朋友们都彼此知道各自的家在什么地方。那时候，两岸已经统一，台湾已经正式回归祖国，成了台湾省。
但是台湾和厦门之间还只有船，没有桥相连，作为政府高层，你为了让自己的朋友们相互拜访更加容易，提出一个方案
在厦门和台湾之间修建一座大桥，联通两岸的居民
现在你已经知道，你的朋友们中，哪几家之间是有大路联通的（无向），没有相连的路的两家不能直接到达，需要经过别的家才可以
题目保证厦门的人两两可以互达，台湾的两两可以互达，两个点之间的距离为欧式距离（直线距离）
你的目标就是确定修建大桥的位置，使得你的这群朋友之中，两两之间串门所花费的最长的时间最少（即距离最短）

注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个人的家相交，我们才认为它们是连通的。

输入文件包括你的朋友的总数、他们各自的家的坐标，还有一个如下的对称邻接矩阵表示每两个人的家之间是否有大路相连（1表示有路相连，0表示没有） ：

   A  B  C  D  E  F  G  H 
A  0  1  0  0  0  0  0  0
B  1  0  1  1  1  0  0  0
C  0  1  0  0  1  0  0  0
D  0  1  0  0  1  0  0  0
E  0  1  1  1  0  0  0  0
F  0  0  0  0  0  0  1  0
G  0  0  0  0  0  1  0  1
H  0  0  0  0  0  0  1  0

Format

Input

第1行: 一个整数N (1 <= N <= 150), 表示你的好朋友数

第2到N+1行: 每行两个整数X,Y (0 <= X ,Y<= 100000), 表示N个好朋友的家的坐标。注意每一户人家的坐标都是不一样的。

第N+2行到第2*N+1行: 每行包括N个数字(0或1) 表示如上文描述的对称邻接矩阵。 输入文件包括至少两个不连通的块

Output

只有一行，包括一个实数，表示所求的距离（最长距离最短）。数字保留六位小数。

Sample 1

Input

8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010

Output

22.071068

Limitation

1s, 1024KiB for each test case.

Hint

样例为下面这个图
左半部分（厦门）两两串门所花时间最长的为A到E(路径为A-B-E)，12.07(5+5√2)
D (15,15) E (20,15)

		D	—	E
		|	/	|
A	—	B	—	C

A(10,10) B(15,10) C(20,10)
右半部分（台湾）为
F(30,15)

		F
	/
G	—	H

G(25,10) H(30,10)

将C和G相连后，A到F的距离最长，为15+5√2，且这个长度为所以其他方案中最长长度最短的。

Source

Coolxxx