eolymp
bolt
Try our new interface for solving problems
Problems

Blowing up the roads

Blowing up the roads

Time limit 1 second
Memory limit 128 MiB

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 data

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 data

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

prb1617.gif

Examples

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