题目描述

假设你想以最美观的方式布置花店的橱窗。现在你有F束不同品种的花束，同时你也有至少同样数量的花瓶被按顺序摆成一行。这些花瓶的位置固定于架子上，并从$1$至$V$顺序编号，$V$是花瓶的数目，从左至右排列，则最左边的是花瓶$1$，最右边的是花瓶$V$。花束可以移动，并且每束花用$1$至$F$间的整数唯一标识。标识花束的整数决定了花束在花瓶中的顺序，如果$I＜J$，则令花束I必须放在花束$J$左边的花瓶中。

例如，假设一束杜鹃花的标识数为$1$，一束秋海棠的标识数为$2$，一束康乃馨的标识数为$3$，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目。则多余的花瓶必须空置，且每个花瓶中只能放一束花。

每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。

在上述例子中，花瓶与花束的不同搭配所具有的美学值，如下表所示

例如，根据上表，杜鹃花放在花瓶$2$中，会显得非常好看；但若放在花瓶$4$中则显得十分难看。

为取得最佳美学效果，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。如果有不止一种的摆放方式具有最大的美学值，你只要输出字典序最小的那种摆放方式。

输入格式

第一行包含两个数：$F$，$V$。

随后的F行中，每行包含$V$个整数，$Aij$ 即为输入文件中第（$i+1 $）行中的第j个数。

$1≤F≤100$，其中$F$为花束的数量，花束编号从$1$至$F$。

$F≤V≤100$，其中$V$是花瓶的数量。

$-50≤Aij≤50$，其中$Aij$是花束$i$在花瓶j中的美学值。

输出格式

一行是程序所产生摆放方式的美学值。

第二行必须用$f$个数表示摆放方式，即该行的第$k$个数表示花束$k$所在的花瓶的编号。

样例数据

input

3 5 
7  23  -5 -24  16
5  21  -4  10  23
-21 5  -4 -20  20

output

53
2  4  5

数据规模与约定

时间限制：$ 1 \text {s}$

空间限制：$ 256 \text {MB}$