Think I'll Buy Me a Football Team

Falling stocks. Bankrupt companies. Banks with no cash. It seems like the best time to invest: "Think I'll buy me a football team!"

No, seriously, I think I have a solution to at least the problem of cash in banks. These days banks owe each other huge amounts of money, and even though on paper they should have enough, no bank has enough cash to pay off the debts of the others. Take, for example, the inter-bank loans shown in figure (a). The graph shows the amounts owed between four banks (A...D). For instance, A owes B 50M while, at the same time, B owes A 150M. (It is quite common for two banks to owe each other at the same time.) A total of 380M in cash is needed to settle all the debts between the banks.

In an attempt to reduce the need for cash, and after studying the example carefully, I concluded that a lot of cash is being transferred unnecessarily. Take a look:

C owes D the same amount as D owes A, so we can say that C owes A 30M and take D out of the picture.
But since A already owes C 100M, we can say that A owes C only 70M.
Similarly, B owes A only 100M (since A already owes B 50M). This reduces the graph above to the one in figure (b), which lowers the needed cash to 190M (a reduction of 200M, or 53%).
I can do even better. Rather than B paying A 100M and A paying 70M to C, B can pay 70M (out of A's 100M) directly to C. This reduces the graph to the one in figure (c). The banks can now settle all their debts with only 120M in cash, a total reduction of 260M, or 68%. Amazing!

I have the data on inter-bank debts, but I can't seem to process it to obtain the minimum amount of cash needed to settle all the debts. Could you please write a program to do that?

The input consists of one or more test cases. Each test case is given on N + 1 lines. The first line holds the number of banks N ($N < 1000$). The remaining N lines give the inter-bank debts as an N x N adjacency matrix (with a zero diagonal) in row-major order. The ith row lists the amounts owed by the ith bank. Amounts on a line are separated by one or more spaces. All amounts are less than 1000.

The last line of the input contains a single 0.

For each test case, print the result in the following format:

k. B A

where k is the test case number (starting at 1), B is the amount of cash needed before reduction, and A is the minimum amount of cash needed after reduction.