Pizza Slice Debt Settlement#1336

Pizza Slice Debt Settlement

1 second

64 megabytes

Very easy

Pizza Crisis in the Lair! Empty pizza boxes everywhere. Four turtles, zero slices left. Master Splinter looks at his students and says: "Perhaps it's time you learned to share pizza more wisely, my sons!"

Okay, so here's the situation. Leonardo, Michelangelo, Donatello, and Raphael have been trading pizza slices with each other all week, and now nobody remembers who owes what to whom. They all owe each other slices, but no turtle has enough slices on hand to pay everyone back, even though mathematically the numbers should work out.

Let me show you the pizza debt situation shown in figure (a). The graph displays how many slices are owed between the four turtles (Leo, Mikey, Donnie, and Raph). For example, Leo owes Mikey $50$ slices, while Mikey owes Leo $150$ slices. (Yeah, it happens - two turtles can owe each other at the same time!) To settle everything, they'd need $380$ pizza slices to pass around.

But wait! After studying this mess, I realized there's a smarter way. We're wasting pizza on unnecessary transfers! Check this out:

Donnie owes Raph exactly $30$ slices, and Raph owes Leo the same $30$ slices. So why not skip the middleman? Donnie can pay Leo directly, and we eliminate Raph from the chain!
But hold on - Leo already owes Donnie $100$ slices. So really, Leo only needs to pay Donnie the difference: $70$ slices.
Same idea with Mikey and Leo. Mikey owes Leo $150$ slices, but Leo owes Mikey $50$ slices. Net result? Mikey pays Leo just $100$ slices. Now we're down to figure (b), and we only need $190$ slices total. That's $200$ slices saved, or $53$ %!
But we can do even better! Instead of Mikey giving $100$ slices to Leo, and then Leo turning around and giving $70$ slices to Donnie, why not have Mikey give $70$ slices directly to Donnie? Then Mikey only gives $30$ slices to Leo. Check out figure (c) - we're down to just $120$ slices needed! That's a $260$ slice reduction, or $68$ %! Cowabunga!

I've got all the data about who owes whom, but I can't figure out the optimal way to minimize the pizza needed. Can you write a program that finds the minimum number of slices required to settle all the debts?

Input

Your program will be tested on one or more test cases. Each test case spans $N + 1$ N+1 lines, where $N < 1000$ N < 1000 is the number of turtles (given on the first line). The next $N$ lines contain an $N \times N$ N \times N matrix where entry $(i, j)$ shows how many slices turtle $i$ owes to turtle $j$ (the diagonal is all zeros since nobody owes themselves). Values are separated by spaces, and all numbers are less than $1000$ . The input ends with a line containing a single $0$ .

Output

For each test case, output:

k. B A

where $k$ is the test case number (starting from $1$ ), $B$ is the total slices needed before optimization, and $A$ is the total slices needed after optimization.

Examples

Example 1