Ancient Azerbaijan#9003
In ancient times, there were reportedly 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 of size N \times N. In this table, the entry A_{ij} represents the shortest path length between city and city .
Your task is to help Barış verify whether such a configuration of cities could have existed. If it is feasible, calculate the minimum sum of the lengths of all the roads.
The first line contains a single integer (1 \le N \le 200), representing the number of cities. This is followed by lines, each containing integers, where A_{ij} (1 \le A_{ij} \le 10^9 for i \ne j, A_{ii} = 0) is the shortest path length between cities and .
If it is impossible to reconstruct such a network of cities, output "-1". Otherwise, output the minimum possible sum of the lengths of all roads.
Example 1
Example 2