# Maximum flow and matchings

# Blowing up the roads

There is a direct bidirectional road between every pair of distinct towns in the country. Peter wants to blow up enough of these roads that there are at least two towns that are no longer connected to each other by any direct or indirect paths.

You are given the cost of blowing up each road. Find the minimal total cost required for Peter to achieve their goal.

#### Input

Consists of multiple test cases. The first line of each test case contains the number **n** (**n** ≤ **50**) of towns in a country. Next **n** lines describe the roads: the **j**-th character of the **i**-th line is a digit representing the cost of blowing up the road from the **i**-th town to the **j**-th town.

#### Output

For each test case print in a separate line the minimal total cost required for Peter to achieve their goal.

4 0911 9011 1109 1190 6 030900 304120 040174 911021 027207 004170 4 0399 3033 9309 9390

4 8 9