e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Задачи

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

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

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

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

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

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

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

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

Лимит времени 1 секунды
Лимит использования памяти 128 MiB
Входные данные #1
4
0911
9011
1109
1190
6
030900
304120
040174
911021
027207
004170
4
0399
3033
9309
9390
Выходные данные #1
4
8
9