Ancient Azerbaijan
In ancient times, there were reportedly N cities in Azerbaijan, connected by two-way roads. Archaeologist Barış discovered that it was possible to travel between any pair of these cities, though direct routes might not have existed between them.
While the details of the direct routes and their lengths have been lost, Barış managed to determine the shortest paths between all pairs of cities and compiled this information into a table A of size N × N. In this table, the entry A[ij] represents the shortest path length between city i and city j.
Your task is to help Barış verify whether such a configuration of N cities could have existed. If it is feasible, calculate the minimum sum of the lengths of all the roads.
Input
The first line contains a single integer N (1 ≤ N ≤ 200), representing the number of cities. This is followed by N lines, each containing N integers, where A[ij] (1 ≤ A[ij] ≤ 10^9 for i≠j, A[ii] = 0) is the shortest path length between cities i and j.
Output
If it is impossible to reconstruct such a network of N cities, output "-1". Otherwise, output the minimum possible sum of the lengths of all roads.