축구팀이나 하나 사 볼까

주가는 폭락하고, 기업은 파산하고, 은행에는 현금이 바닥났다. 지금이야말로 투자하기 좋은 때인 것 같다. "축구팀이나 하나 사 볼까!"

농담이 아니라, 적어도 은행의 현금 부족 문제만큼은 해결할 방법이 있는 것 같다. 요즘 은행들은 서로 막대한 금액을 빚지고 있는데, 장부상으로는 충분한 돈이 있음에도 다른 은행의 빚을 갚을 현금이 부족하다. 예를 들어 그림 (a)에 나타난 은행 간 대출을 보자. 이 그래프는 네 은행 A~D 사이에 오가는 채무 금액을 나타낸다. 예컨대 A는 B에게 50M을 빚지고 있고, 동시에 B는 A에게 150M을 빚지고 있다. (두 은행이 서로 동시에 빚을 지는 일은 흔하다.) 모든 채무를 정산하려면 총 380M의 현금이 필요하다.

현금 수요를 줄이기 위해 예제를 자세히 살펴본 결과, 불필요하게 오가는 현금이 많다는 것을 알게 되었다. 다음을 보자.

C가 D에게 빚진 금액과 D가 A에게 빚진 금액이 같으므로, D를 빼고 C가 A에게 30M을 빚진 것으로 볼 수 있다.
그런데 A가 이미 C에게 100M을 빚지고 있으므로, 결국 A가 C에게 70M을 빚진 것으로 정리된다.
마찬가지로 B는 A에게 100M만 빚진 셈이 된다. (A가 이미 B에게 50M을 빚지고 있으므로.) 이렇게 하면 그래프가 그림 (b)처럼 줄어들어 필요한 현금이 190M으로 감소한다. (200M, 즉 53% 감소.)
여기서 더 줄일 수 있다. B가 A에게 100M을 주고 A가 다시 C에게 70M을 주는 대신, B가 (A가 갚을 100M 중) 70M을 곧바로 C에게 줄 수 있다. 그러면 그래프는 그림 (c)처럼 줄어들고, 은행들은 단 120M의 현금만으로 모든 채무를 정산할 수 있다. 총 260M, 즉 68% 감소다. 놀랍다!

은행 간 채무 데이터는 있지만, 이를 처리해 모든 채무를 정산하는 데 필요한 최소 현금을 구하지 못하고 있다. 이 값을 계산하는 프로그램을 작성하라.

입력은 하나 이상의 테스트 케이스로 이루어진다. 각 테스트 케이스는 N + 1개의 줄로 주어진다. 첫 줄에는 은행의 수 N ($N < 1000$)이 주어진다. 이어지는 N개의 줄은 은행 간 채무를 나타내는 N × N 인접 행렬을 행 우선(row-major) 순서로 담고 있으며, 대각선 원소는 모두 0이다. i번째 행은 i번째 은행이 다른 은행들에게 빚진 금액을 나타낸다. 한 줄의 금액들은 하나 이상의 공백으로 구분된다. 모든 금액은 1000 미만이다.

입력의 마지막 줄에는 0 하나만 주어진다.

각 테스트 케이스마다 다음 형식으로 결과를 출력한다.

k. B A

여기서 k는 테스트 케이스 번호(1부터 시작), B는 정산 전에 필요한 현금 금액, A는 정산 후에 필요한 최소 현금 금액이다.