/*

Little Shop of Flowers (IOI 1999)
Copyright (C) 2000 Sebastiano Vigna

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA




Il problema viene risolto mediante programmazione dinamica, e piu`
precisamente riducendo il problema di disporre ottimalmente mazzi di fiori
m_1,...,m_r in vasi v_1,...,v_s con s>=r al problema di disporre ottimalmente
i mazzi m_t,...,m_r nei vasi v_u,...,v_s con 1<=t<=r e 1<=u<=s.

*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>

#define MAXFIORI 100
#define MAXVASI  100

#define max(a,b) ((a)>(b)?(a):(b))

int M[MAXFIORI][MAXVASI];  /* Tabella riempita tramite programmazione dinamica */

int A[MAXFIORI][MAXVASI];  /* Valori estetici per ogni tipo di mazzo e di vaso */
int U[MAXFIORI][MAXVASI];  /* Matrice di valori booleani: se U[i][j] allora
									nella soluzione ottima per il problema ridotto il
									mazzo i e` *usato* nel vaso j. Piu` precisamente,
									se U[i][j'] (j'<j) e` il primo elemento a 1 prima di
									U[i][j] allora per tutte le soluzioni ottime con
									indici <i,j'> < <i,k> <= <i,j> il mazzo i e`
									inserito nel vaso k. */

int main(int argc, char *argv[]) {

	int F, V, i, j;

	scanf("%d %d\n", &F, &V);     /* Innanzitutto leggiamo i dati dentro A. */
	for(i=0; i<F; i++) {
		for(j=0; j<V; j++)
			scanf("%d", &A[i][j]);
		scanf("\n");
	}

	/* Riempiamo l'ultima riga. M[F-1][j] rappresenta la migliore soluzione
		ottenibile utilizzando solo l'ultimo mazzo e ponendolo a partire dal
		vaso j.  Quindi in generale il valore di M[F-1][j] e il massimo tra il
		valore ottenuto mettendo l'ultimo mazzo nel posto j e il valore
		M[F-1][j+1]. Se il massimo e` realizzato dal primo valore registriamo
		questo fatto in U. */

	for(j=V-1; j>=0; j--) {
		if (j == V-1 || A[F-1][j] > M[F-1][j+1]) {
			M[F-1][j] = A[F-1][j];
			U[F-1][j] = 1;
		}
		else M[F-1][j] = M[F-1][j+1];
	}

	/* Possiamo ora riempire le altre righe della tabella. Per calcolare
		M[i][j] massimizziamo tra la soluzione ottenuta in M[i][j+1] (cioe`
		se non utilizzassimo il vaso corrente) e la soluzione che si ottiene
		inserendo il mazzo i nel posto j e sommando la soluzione ottima per i
		rimanenti (e cioe` M[i+1][j+1]). In quest'ultimo caso registriamo nella
		matrice U l'utilizzo del vaso. */

	for(i=F-2; i>=0; i--) {
		for(j=V-1-(F-1-i); j>=0; j--) { /* Non ha senso utilizzare meno vasi
														che mazzi! */
			if (j==V-1-(F-1-i) || A[i][j]+M[i+1][j+1] > M[i][j+1]) {
				M[i][j] = A[i][j]+M[i+1][j+1];
				U[i][j] = 1;
			}
			else M[i][j] = M[i][j+1];
		}
	}

	/* Alla fine, M[0][0] e` la soluzione ottima utilizzando tutti i mazzi a
		partire dal vaso 0, e quindi in posizione arbitraria. */

	printf("%d\n", M[0][0]);

	/* E` anche facile, a partire da U, ricostruire la soluzione: scandiamo la
		riga corrente fino a trovare un elemento di U a 1 (il che vuol dire che
		il mazzo corrispondente alla riga corrente e` stato inserito nel vaso
		corrente), e quindi passiamo alla riga sottostante, una posizione piu`
		oltre. */

	for(j=i=0; i<F; i++) {
		for( ; j<V; j++)
			if (U[i][j]) {
				printf("%d ", j+1); /* L'output e` richiesto con indicizzazione
												a partire da _uno_! */
				j++;
				break;
			}
	}
}