Є \(N\) міст, деякі міста з'єднані двосторонніми дорогами. З будь-якого міста можна потрапити в будь-яке інше використовуючи дороги.
Вам задана карта найкоротших шляхів між всіма парами міст. Визначіть, чи є ця карта правильною. Тобто чи існує такий набір доріг між містами, що найкоротші шляхи будуть відповідати знайденій карті.

Формат вхідних даних

В першому рядку ціле число \(N\) (\(1 \le N \le 300\))
Далі йде матриця з \(N\) рядків та \(N\) стовпчиків. Число в рядку \(R\) та стовпчику \(C\) означає довжину найкоротшого шляху між містами \(R\) та \(C\).

Формат вихідних даних

Якщо існує такий набір доріг, який відповідає знайденій карті, виведіть найкоротшу сумарну довжину доріг. Якщо такого набору не існує, виведіть -1.

Приклад вхідних даних-1

3
0 1 3
1 0 2
3 2 0

Приклад вихідних даних-1

3

Пояснення до прикладу-1

Можливий приклад мережі доріг який відповідає карті:
Міста 1 та 2 з'єднані дорогою довжини 1
Міста 2 та 3 з'єднані дорогою довжини 2
Міста 3 та 1 не з'єднані дорогою

Приклад вхідних даних-2

3
0 1 3
1 0 1
3 1 0

Приклад вихідних даних-2

-1