# Зчитування вхідних даних
file = File.open("profit.in","r")
(m, n)=file.readline.split
m = m.to_i
n = n.to_i
a = []
a.push([0]*(n+1))
for j in 1..m
  a.push([0])
  t=file.readline.split
  for k in 1..n
    a[j].push(t[k-1].to_i)
  end
end
file.close

x=[0]
for j in 0...n
  x.push(0)
end

# створення 2-вимірного масиву,
# заповненого нулями  
def zero2(n,m)
  f=[]
  f.push([0]*(m+1))
  for j in 1..n
    f.push([0])
    for k in 1..m
      f[j].push(0)
    end
  end
  return f
end

f=zero2(n,m)
q=zero2(n,m)

# Заповнення f даними від банкіра 1
for j in 0..m
  f[1][j]=a[j][1]  
  q[1][j]=j
end

# Заповнення f даними від банкірів 2-n
for i in 2..n
  for j in 1..m
    p=0
    for k in 0..j
      if (f[i-1][j-k]+a[k][i]>p)
        p=f[i-1][j-k]+a[k][i]
        l=k
      end
    end
    f[i][j]=p
    q[i][j]=l
  end
end

p=f[n][m]
i=n

# Визначення оптимального розподілу коштів
while (m!=0)
  x[i]=q[i][m]
  m=m-x[i]
  i-=1
end

# Запис відповіді
file = File.open("profit.out","w")
file.puts p
for i in 1...n
  file.write(x[i].to_s+' ')
end
file.puts x[n].to_s
file.close()