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

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

Вхідні дані

Складається з декількох тестів. Перший рядок кожного тесту містить кількість n (n ≤ 50) міст у країні. Наступні n рядків описують дороги: j-ий символ i-го рядка є цифрою, яка задає вартість знищення дороги, що веде з i-го міста в j-ий.

Вихідні дані

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