题目描述

有 N 个景点，编号为 1 ~ N，分布在多个景区内。编号为 i 的景点的坐标为 $(Xi,Yi)$。任意两个景点的位置互不相同。同一个景区内的景点之间有一些双向通行的笔直道路把它们连通起来，长度即为两点间的欧几里得距离。不同景区的景点间没有道路。

为了衡量一个景区的游玩时间，现定义一个景区的“时间复杂度”为：该景区内任意两个景点间的最短路径长度中，最大的那一个长度。

现在政府部门进行资源整合，想在某两个景区中各选一个景点，在两个景点间修建一条笔直的道路，把这两个景区连成一个景区。

同时，政府部门希望得到的新景区的“时间复杂度”尽可能小。

你知道这个最小“时间复杂度”是多少吗？

注：如果两条道路在非景点处相交，中途是不能换路的。

输入格式

第一行：$N$

接下来 $N$ 行：每行两个整数 $Xi,Yi$

接下来是一个 $N×N$ 的 01 字符矩阵 $A$。若 $A_{i,j}=$ 1，表示景点 $i$ 和 $j$ 之间有一条笔直的道路，否则表示景点 $i$ 和 $j$ 之间没有道路。数据保证 $A_{i,j} = A_{j,i}$。

输出格式

一个实数，表示能得到的最小“时间复杂度”。保留 6 位小数。

样例输入

6
2 3
3 3
2 2
3 2
1 1
10 10
010000
100100
000010
010000
001000
000000

样例输出

3.828427

数据范围

$1 ≤ N ≤ 150$， $0 ≤ Xi ,Yi ≤ 10^5$