19043번 - Balance 스페셜 저지다국어

문제

We say that a matrix $A$ of size $N \times N$ is 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$. Your task is to output another matrix $B$ of equal size such that $B$ is balanced and $B[i][j] \ge A[i][j]$ for all 1ドル \le i, j \le N$. Furthermore, your $B$ must have the minimum possible sum of entry values.

입력

The first line of input 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 values of the balanced matrix $B$ you found. On the next $N$ lines, print the balanced matrix in the same format as given in the input.

Any output matrix that meets the constraints described in the statement will be accepted. The values of the output matrix are not constrained in any way (specifically, they may exceed the value 35ドル,000円$).

제한

힌트