По данным из неизвестных источников, в древние времена в Азербайджане было N городов. Между некоторыми из этих городов проходили двухсторонние дороги. По находкам археолога Барыша, стало известно, что из любого из этих N городов было возможно путешествовать в любой другой (прямого пути между ними могло и не быть).

К сожалению, информация о прямых путях между городами и длинами этих путей была потеряна, но Барыш продолжил свои исследования обнаружив кратчайшие пути между всеми городами и построил соответствующую таблицу A размеров N × N . В этой таблице число Aij означает кратчайший путь между городами i и j .

Основываясь на полученных данных, помогите Барышу понять могли ли существовать N таких городов. Если это возможно, найдите минимальную сумму длин всех дорог.

Входные данные

В первой строке одно целое число N (1 ≤ N ≤ 200) – количество городов, далее следует N строк по N чисел в каждой, где Aij (1 ≤ Aij ≤ 109(i≠j), Aii = 0) – длина кратчайшего пути между городами i и j .

Выходные данные

В случае если невозможно найти N городов, выведите "-1". В противном случае выведите минимальную возможную сумму длин всех дорог.