Migrated from Lutece 2689 齐木楠雄的Ψ难

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

齐木楠雄是一位超能力者，今天他要参加期末考试。作为一名无所不能的超能力者，无论出什么样的题，都难不到他。用透视能看到别人的试卷，用心灵感应可以知道所有人的想法，用意念投影可以迅速填完答案。不过千万不要误会，即使不用超能力，齐木楠雄也能自己做对所有题。他用超能力作弊只是为了得到一个不惹眼的分数。

期末考试将会持续 $5$ 小时，在这 $5$ 小时内，需要完成 $m$ 门科目的作答，中途没有休息时间。除齐木楠雄外，有 $n$ 位同学会参加考试。齐木楠雄认为，两个人的考试成绩的差距是每一门科目的分数差的绝对值之和。齐木楠雄想要让自己和所有同学的考试成绩的差距之和最小，并且在成绩的差距之和最小的前提下总分最小，因为他认为这样的分数是最不惹眼的分数。

齐木楠雄想拜托你帮他计算出他每一门应该得到多少分。他会在考试结束前一秒用透视看到所有同学的答案并且给他们评分，然后他会把所有同学每一门科目的分数告诉你，你需要在一秒内完成计算，并把每一门应该得到的分数告诉他，他会用意念投影瞬间完成作答。

Input

第一行有两个整数 $n,m\ (1\le n,m\le 1000,1\leq n\times m \leq 1000)$。

接下来 $n$ 行，每一行有 $m$ 个整数分别是 $a_{i,1}, a_{i,2}, \ldots , a_{i,m}\ (1 \leq a_{i,j} \leq 1000)$，表示第 $i$ 位同学在第 $j$ 门科目得到的分数。

Output

第一行输出一个整数，表示成绩的差距之和的最小值。

第二行输出 $m$ 个整数，第 $i$ 个数 $b_i$ 表示第 $i$ 门科目齐木楠雄希望得到的分数。可以保证在题目要求下，齐木楠雄希望得到分数的值是唯一的。

Samples

3 2
1 4 
3 9
3 1

10
3 4

Note

在样例中，齐木楠雄希望在第一门科目得到 $3$ 分，第二门科目得到 $4$ 分。第一个同学和齐木楠雄的成绩的差距是 $|1 - 3| + |4 - 4| = 2$，第二个同学和齐木楠雄的成绩的差距是 $|3 - 3| + |9 - 4| = 5$，第三个同学和齐木楠雄的成绩的差距是 $|3 - 3| + |1 - 4| = 3$。总差距之和是 $10$。

Resources

电子科技大学第十二届 ACM 趣味程序设计竞赛