Falling Stocks. Bankrupted companies. Banks with no Cash. Seems like the best time to invest: "Think I'll buy me a football team!" No seriously, I think I have the solution to at least the problem of cash in banks. Banks nowadays are all owing each other great amounts of money and no bank has enough cash to pay other banks' debts even though, on paper at least, they should have enough money to do so. Take for example the inter-bank loans shown in figure (a). The graph shows the amounts owed between four banks (\textbf{A}...\textbf{D}). For example, \textbf{A} owes \textbf{B} \textbf{50M} while, at the same time, \textbf{B} owes \textbf{A} \textbf{150M.} (It is quite common for two banks to owe each other at the same time). A total amount of \textbf{380M} in cash is needed to settle all debts between the banks. \includegraphics{https://static.e-olymp.com/content/3e/3ecfc5273212a72fb5ebf80f1033d8e554b49591.jpg} In an attempt to decrease the need for cash, and after studying the example carefully, I concluded that there's a lot of cash being transferred unnecessarily. Take a look: \begin{enumerate} \item \textbf{C} owes \textbf{D} the same amount as \textbf{D} owes \textbf{A}, so we can say that \textbf{C} owes \textbf{A} an amount of \textbf{30M} and get \textbf{D} out of the picture. \item But since \textbf{A} already owes \textbf{C} \textbf{100M}, we can say that \textbf{A} owes \textbf{C} an amount of \textbf{70M}. \item Similarly, \textbf{B} owes \textbf{A} \textbf{100M} only, (since \textbf{A} already owes \textbf{B} \textbf{50M}). This reduces the above graph to the one shown in figure (b) which reduces the needed cash amount to \textbf{190M} (\textbf{A} reduction of \textbf{200M}, or \textbf{53}\%). \item I can still do better. Rather than \textbf{B} paying \textbf{A} \textbf{100M} and \textbf{A} paying \textbf{70M} to \textbf{C}, \textbf{B} can pay \textbf{70M} (out of \textbf{A}'s \textbf{100M}) directly to \textbf{C}. This reduces the graph to the one shown in figure (c). Banks can settle all their debts with only \textbf{120M} in cash. A total reduction of \textbf{260M} or \textbf{68}\%. Amazing! \end{enumerate} I have data about inter-bank debts but I can't seem to be able 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? \InputFile Your program will be tested on one or more test cases. Each test case is specified on \textbf{N}+\textbf{1} lines where \textbf{N} < \textbf{1000} is the number of banks and is specified on the first line. The remaining N lines specifies the inter-bank debts using an \textbf{N}×\textbf{N} adjacency matrix (with zero diagonal) specified in row-major order. The ith row specifies the amounts owed by the ith bank. Amounts are separated by one or more spaces. All amounts are less than \textbf{1000}. The last line of the input file has a single \textbf{0}. \OutputFile For each test case, print the result using the following format: \textbf{k. B A} where \textbf{k} is the test case number (starting at \textbf{1}), is a space character, B is the amount of cash needed before reduction and \textbf{A} is the amount of cash after reduction.