Cable Donation

Dasom has many spare LAN cables at home. She wants to keep only enough cables so that the computers in all N rooms can communicate with one another, and donate the rest.

Each room has exactly one computer. Two computers can communicate if they are connected directly by a cable, or if they can reach each other through other computers.

The input describes the cables Dasom currently has. Each non-0 character represents one cable between the two computers at that matrix position. If there are multiple cables between the same two computers, only the cables needed for connectivity have to be kept; cables from a computer to itself do not help connectivity.

Find the maximum total length of cable Dasom can donate while still making all computers mutually reachable.

The first line contains the number of computers, N.

The next N lines describe the cables. If the jth character of the ith line is 0, there is no cable connecting computer i and computer j. Any other character gives the cable length.

Lowercase letters a through z represent lengths 1 through 26, respectively. Uppercase letters A through Z represent lengths 27 through 52, respectively.

N is a positive integer not greater than 50.

Print the maximum total length of cable Dasom can donate.

If it is impossible to make all computers mutually reachable, print -1.