Давній Азербайджан
У давні часи в Азербайджані існувало N міст, між якими проходили двосторонні дороги. Археолог Бариш виявив, що з будь-якого з цих N міст можна було дістатися до будь-якого іншого, хоча прямого шляху між ними могло не бути.
На жаль, інформація про прямі дороги та їх довжини була втрачена. Однак, Бариш зміг знайти найкоротші шляхи між усіма містами і створив таблицю A розміром N × N. У цій таблиці значення A[ij] представляє найкоротший шлях між містами i та j.
Ваша задача — допомогти Баришу визначити, чи могли існувати такі N міст. Якщо це можливо, знайдіть мінімальну суму довжин усіх доріг.
Вхідні дані
Перший рядок містить одне ціле число N (1 ≤ N ≤ 200) — кількість міст. Далі йдуть N рядків, кожен з яких містить N чисел, де A[ij] (1 ≤ A[ij] ≤ 10^9 для i≠j, A[ii] = 0) — довжина найкоротшого шляху між містами i та j.
Вихідні дані
Якщо неможливо відновити N міст, виведіть "-1". Інакше, виведіть мінімальну можливу суму довжин усіх доріг.