Balance

A matrix $A$ of size $N \times N$ is called balanced if $A[i][j] + A[i + 1][j + 1] = A[i + 1][j] + A[i][j + 1]$ for all $1 \le i, j \le N - 1$.

You are given a matrix $A$ of size $N \times N$. Output a matrix $B$ of the same size such that $B$ is balanced and $B[i][j] \ge A[i][j]$ for all $1 \le i, j \le N$. In addition, the sum of the entries of $B$ must be as small as possible.

The first line contains an integer $N$, the number of rows and columns of the matrix ($1 \le N \le 50$).

Each of the following $N$ lines contains $N$ integers. Together they describe the matrix $A$. It is guaranteed that $0 \le A[i][j] \le 35\,000$ for all $1 \le i, j \le N$.

On the first line, print the sum of the entries of the balanced matrix $B$ you found. On the next $N$ lines, print the balanced matrix in the same format as the input.

Any matrix satisfying the conditions described in the statement is accepted. The values of the output matrix are not constrained in any way (in particular, they may exceed $35\,000$).