eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Разрушение дорог

Разрушение дорог

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Между каждой парой городов страны имеется прямая двусторонняя дорога. Петр хочет взорвать такое количество дорог, чтобы образовалось хотя бы два города, проезд между которыми был невозможен.

Вам известна стоимость подрыва каждой дороги. Найти наименьшую стоимость, за которую Петру удастся совершить задуманное.

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

Состоит из нескольких тестов. Первая строка каждого теста содержит количество n (n50) городов в стране. Следующие n строк описывают дороги: j-ый символ i-ой строки является цифрой, задающей стоимость уничтожения дороги, ведущей из i-го города в j-ый.

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

Для каждого теста вывести в отдельной строке наименьшую стоимость, за которую Петру удастся совершить задуманное.

prb1617.gif

Пример

Входные данные #1
4
0911
9011
1109
1190
6
030900
304120
040174
911021
027207
004170
4
0399
3033
9309
9390
Выходные данные #1
4
8
9