Il negozio di fiori

Si vuole allestire la vetrina di un negozio di fiori in un modo gradevole. Si dispone di F mazzi di fiori, ciascuno di un genere diverso, e almeno altrettanti vasi ordinati in una fila. I vasi sono incollati sopra a una mensola e sono numerati consecutivamente da 1 a V, dove V è il numero di vasi, disposti da sinistra a destra in modo che il vaso 1 è quello più a sinistra e il vaso V quello più a destra. I mazzi si possono spostare e sono identificati da un numero intero tra 1 e F. Questi numeri hanno un significato: determinano l'ordine richiesto di presentazione dei mazzi di fiori nella fila di vasi. Infatti, il mazzo i deve essere in un vaso alla sinistra di quello che contiene il mazzo j ogni qualvolta i < j.

Supponiamo, per esempio, di avere un mazzo di azalee (id=1), un mazzo di begonie (id=2) ed un mazzo di garofani (id=3). Ora, tutti i mazzi devono essere messi nei vasi mantenendo l'ordine dei loro id. Il mazzo di azalee deve essere messo in un vaso alla sinistra delle begonie, e il mazzo di begonie in un vaso alla sinistra dei garofani. Se ci sono più vasi che mazzi di fiori allora i vasi eccedenti vengono lasciati vuoti. Un vaso può contenere solo un mazzo di fiori.

Ciascun vaso ha una distinta caratteristica (esattamente come i fiori). Dunque, mettere un mazzo di fiori in un vaso ha come risultato un determinato valore estetico, espresso da un numero intero. I valori estetici sono mostrati nella tabella che segue. Lasciare un vaso vuoto ha un valore estetico di 0.

		V A S I
		1	2	3	4	5
Mazzi	1 (azalee)	7	23	-5	-24	16
	2 (begonie)	5	21	-4	10	23
	3 (garofani)	-21	5	-4	-20	20

Secondo la tabella, l'azalea apparirebbe molto bene nel vaso 2, ma sarebbe esteticamente sgradevole nel vaso 4.

Raggiungere l'effetto più gradevole corrisponde alla massimizzazione della somma dei valori estetici per la sistemazione dei mazzi di fiori. Se più di una sistemazione ha il valore della somma massima, qualsiasi sistemazione tra queste sarà accettabile. Si deve produrre una sola sistemazione.

Assunzioni

1 <= F <= 100, dove F è il numero dei mazzi di fiori. I mazzi sono numerati da 1 a F.
F <= V <= 100, dove V è il numero di vasi.
-50 <= A_ij <= 50, dove A_ij è il valore estetico ottenuto mettendo il mazzo i di fiori nel vaso j.

Dati in input

L'input è un file di testo chiamato flower.inp.

La prima linea contiene 2 numeri: F e V.
Seguono F linee, ciascuna contenente V numeri interi: A_ij è dato come il j-esimo numero della (i+1)-esima linea del file di input.

Dati in output

L'output deve essere un file di testo di nome flower.out che consiste in due linee:

La prima riga conterrà la somma dei valori estetici della sistemazione.
La seconda riga dovrà presentare la sistemazione come un elenco di F numeri: il k-esimo numero su questa riga identifica il vaso nel quale il mazzo k è stato posto.

Esempio di input e output

flower.inp:

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

flower.out:
```
2 4 5
```

Valutazione

Al programma è concesso un tempo di esecuzione di 2 secondi.

Non sono previsti punteggi parziali.