Competitions

# Maximum flow and matchings

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 (n50) 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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4
0911
9011
1109
1190
6
030900
304120
040174
911021
027207
004170
4
0399
3033
9309
9390

Output example #1
4
8
9