取整矩阵

给定一个边长为 $N$ 的实数增广矩阵。记左上角的 $(N-1)\times(N-1)$ 个元素为 $A_{i,j}$，其中 $1\le i,j<N$；末列元素为 $B_i$，其中 $1\le i<N$；末行元素为 $C_j$，其中 $1\le j<N$；右下角元素为 $0$。

输入保证：

$$B_i=\sum_{j=1}^{N-1}A_{i,j},\qquad C_j=\sum_{i=1}^{N-1}A_{i,j}.$$

需要将矩阵中的每个元素分别替换为其原值的向下取整或向上取整。取整后，矩阵仍须满足：

$$B'_i=\sum_{j=1}^{N-1}A'_{i,j},\qquad C'_j=\sum_{i=1}^{N-1}A'_{i,j}.$$

求取整后整个 $N\times N$ 增广矩阵中所有元素之和的最大值。

输入格式

第一行输入一个整数 $N$。

接下来 $N$ 行，每行输入 $N$ 个实数，表示上述增广矩阵。输入保证末列、末行与左上角矩阵满足题目描述中的行和、列和关系，且右下角元素为 $0$。

所有实数均使用普通十进制记法输入，不使用科学计数法，小数点后至多有 $15$ 位。

输出格式

输出一个整数，表示取整后整个增广矩阵中所有元素之和的最大值。

样例输入

4
3.1 6.8 7.3 17.2
9.6 2.4 0.7 12.7
3.6 1.2 6.5 11.3
16.3 10.4 14.5 0

样例输出

129

数据范围

• $1\le N\le 100$；
• 对所有 $1\le i,j<N$，有 $\lvert A_{i,j}\rvert\le 1000$；
• 由求和关系可知，$\lvert B_i\rvert,\lvert C_j\rvert\le (N-1)\times 1000$；
• 右下角元素为 $0$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

4
3.1 6.8 7.3 17.2
9.6 2.4 0.7 12.7
3.6 1.2 6.5 11.3
16.3 10.4 14.5 0

输出

129