题目描述

给定一个 $N \times N$ 的方阵，元素均为正整数：

$$\begin{matrix} c_{11},c_{12},\dots,c_{1N}\\ c_{21},c_{22},\dots,c_{2N}\\ \cdots\\ c_{N1},c_{N2},\dots,c_{NN} \end{matrix}$$

请编写程序 matrix，寻找两组非负整数序列：

$$m_1,m_2,\dots,m_N$$

和

$$w_1,w_2,\dots,w_N,$$

使得对于每一对 $(i,j)$，都有

$$m_i+w_j \ge c_{ij}$$

并且总和

$$\sum_{i=1}^{N} m_i+\sum_{i=1}^{N} w_i$$

最小。

输入格式

从标准输入读入以下数据：

第一行输入一个整数 $N$，表示矩阵大小。

接下来 $N$ 行给出矩阵的各行。第 $i$ 行包含 $N$ 个正整数，用空格分隔，表示矩阵第 $i$ 行的数字。

输出格式

第一行输出计算得到的最小总和：

$$\sum_{i=1}^{N} m_i+\sum_{i=1}^{N} w_i.$$

第二行输出 $N$ 个非负整数，用单个空格分隔，表示一种可行的序列

$$m_1,m_2,\dots,m_N.$$

第三行输出 $N$ 个非负整数，用单个空格分隔，表示一种可行的序列

$$w_1,w_2,\dots,w_N.$$

输出的两组序列必须满足：

• 它们的总和等于第一行输出的最小总和；
• 对所有 $(i,j)$ 都满足 $m_i+w_j \ge c_{ij}$。

数据范围

• $1 \le N \le 200$；
• $1000 \le c_{ij} \le 100000$；
• 内存限制：$1$ MB。

样例

输入

5
1000 2000 6000 3000 4000
2000 5000 6000 2000 2000
1500 2000 6000 2000 3500
4000 2000 6000 1000 3000
2500 4500 6000 2000 2000

输出

21500
500 0 0 0 0
4000 5000 6000 2500 3500