Bob is about to visit N of his friends' houses. Each house is depicted as a point (xi,yi) on the X−Y plane. The length of roads between two houses i and j is defined as F(i,j)=(xi−xj)2+(yi−yj)2.
There's a N×N matrix M filled with 1s and 0s. M[i][j]=1 denotes that it is possible to travel to ith House from jth House and vice versa. If M[i][j]=0, it is not possible to travel to ith House from jth House and vice versa.
Now, Bob wants to visit all the houses, but the sum of length of all roads traveled should be maximum. There's one more restriction, he can use a maximum of (N−1) roads. Before starting the trip, he would like to know what is the maximum distance he can travel which satisfies all the given conditions. If it is not possible to visit all the houses, print out -1.
Input Format:
The first line contains N, the number of houses Bob wants to visit.
N lines follow, each contains two space separated integers xi and yi which denotes the of the ith house on the X−Y plane.
Again, N lines follow, each contains N space separated integers, each being 0 or 1, denoting the matrix M.
Output Format:
Print the required answer in one line.
Input Constraints:
1≤N≤3000
−106≤xi,yi≤106
Note:
One road can be traversed any number of times , but its contribution would be taken only once. Also, there's large input data, please use faster i/o methods.
This is the image for the given sample. Every house also has a road of length 0 to itself. We can use at max 2 roads which would be from (1,2) -> (8,8) -> (4,5). The total cost is 85 + 25 = 110.