i,j,k,m,n,f,v,t:longint;
a:array[1..100,1..100]of longint;//原始数据
d:array[0..100,0..100]of longint;//动归数组,本来想用 f 的,结果题目花朵数用了
p:array[1..100]of longint;//用来记录第 i 个花瓶中插哪朵花
BEGIN
assign(input,'496.txt'); reset(input);//我在本地测试用
readln(f,v);//花朵数,花瓶数
for i:=1 to f do
for j:=1 to v do read(a[i,j]);//读入原始数据
for i:=1 to f do//先考虑前几朵花
for j:=1 to v do//再考虑前几个花瓶
if j<i then continue else//明显没法插嘛
if i=j then d[i,j]:=d[i-1,j-1]+a[i,j]//明显必须插啊
else if d[i,j-1]>d[i-1,j-1]+a[i,j] then d[i,j]:=d[i,j-1]
else d[i,j]:=d[i-1,j-1]+a[i,j];//考虑第 i 朵花插不插
writeln(d[f,v]);//前 f 朵花 插前 v 个花瓶中的 最优
i:=f; j:=v; t:=0;// i 表示第几朵花, j 表示第几个花瓶
while (i>0)and(j>0) do
begin
if d[i,j]<>d[i,j-1] then//明显第 i 朵花插到了 第 j 个花瓶中
begin
inc(t);
p[t]:=j;//记录一下
dec(i);//减少花束一朵
end;
dec(j);//查看前一个花瓶是否有花
end;
for i:=v downto 2 do
if p[i]<>0 then//花瓶不是空
write(p[i],' ');
writeln(p[1]);
END.