Руйнування доріг
Дуже проста
Обмеження на час виконання 1 секунда
Обмеження на використання пам'яті 128 мегабайтів
Між кожною парою міст країни є пряма двостороння дорога. Петро хоче підірвати таку кількість доріг, щоб утворилося хоча б два міста, проїзд між якими був би неможливий.
Вам відома вартість підриву кожної дороги. Знайти найменшу вартість, за яку Петру вдасться здійснити задумане.
Вхідні дані
Складається з декількох тестів. Перший рядок кожного тесту містить кількість n (n ≤ 50) міст у країні. Наступні n рядків описують дороги: j-ий символ i-го рядка є цифрою, яка задає вартість знищення дороги, що веде з i-го міста в j-ий.
Вихідні дані
Для кожного тесту вивести в окремому рядку найменшу вартість, за яку Петру вдасться здійснити задумане.
Приклади
Вхідні дані #1
Відповідь #1
Відправки 2K
Коефіцієнт прийняття 42%