Chess

Pawełek is still learning chess and is currently working on how the rook moves. So far he only knows that a rook moves horizontally: it can move to any cell in its own row, and to no other cell.

Using this knowledge, Pawełek invented his own game. He draws a square $n \times n$ board and writes one integer in each cell. Then he places some rooks on the board, trying to make the sum of the numbers on the occupied cells as large as possible. He may place any number of rooks (he can always borrow more if he needs them), and if he places none, the sum is taken to be $0$.

To keep the game from being too easy, he follows one rule: no two rooks may occupy the same cell, and no two rooks may attack each other. By the rules he knows, a rook attacks along its own row, so in effect no two rooks may be placed in the same row.

Given the size of the board and the numbers written in its cells, find the largest sum Pawełek can obtain by placing rooks according to these rules.

The first line contains an integer $n$ ($1 \le n \le 200$), the height and width of the board. Each of the next $n$ lines describes one row of the board, in order: the $i$-th of these lines contains $n$ integers separated by spaces, the values written in the cells of the $i$-th row. Each integer is between $-1{,}000{,}000$ and $1{,}000{,}000$, inclusive.

Print a single integer: the maximum sum Pawełek can obtain.