K. Move Stone
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an $$$n \times n$$$ grid. Each cell initially contains some number of stones, such that the total number of stones is exactly $$$n^2$$$.

In one move, you may take a single stone and move it to any other cell in the same row or the same column.

Your goal is to minimize the number of moves needed to make each cell contain exactly one stone.

Input

The first line contains an integer $$$n$$$, representing the size of the grid.

Followed by $$$n$$$ lines, the $$$i$$$-th of which contains $$$n$$$ integers, the $$$j$$$-th integer $$$a_{i, j}$$$ represents the number of stones in cell $$$(i, j)$$$.

  • $$$1 \leq n \leq 500$$$
  • $$$0 \leq a_{i,j} \leq n^2$$$
  • The initial number of stones is exactly equal to the number of cells on the board.
Output

Output a single integer, the minimum number of moves required to make each cell contain exactly one stone.

Examples
Input
3
0 1 2
0 2 2
1 1 0
Output
3
Input
5
1 2 4 0 1
2 0 0 2 0
1 4 1 0 1
2 0 0 0 0
1 2 0 1 0
Output
11