Rezolvare PBinfo #4530

Vrei să-ți aranjezi vitrina florăriei în cel mai minunat mod cu putință. Ai F buchete de flori de diferite soiuri și cel puțin la fel de multe vaze aliniate pe un rând. Vazele sunt lipite de raft și sunt numerotate de la stânga la dreapta cu numere de la 1 la V, unde V este numărul de vaze.

Buchetele pot fi mutate și sunt identificate în mod unic prin numere întregi între 1 și F. Aceste numere de identificare au o semnificație: ele determină ordinea necesară de apariție a buchetelor de flori în rândul de vaze, astfel încât buchetul i trebuie să fie într-o vază aflată șa stânga vazei care conține buchetul j ori de câte ori i < j. Să presupunem, de exemplu, că aveți un buchet de azalee (numerotat cu 1), un buchet de begonii (numerotat cu 2) și un buchet de garoafe (numerotat cu 3). Acum, toate buchetele trebuie puse în vaze păstrându-și numerele de identificare ordonate. Buchetul de azalee trebuie să fie într-o vază în stânga begoniilor, iar buchetul de begonii trebuie să fie într-o vază în stânga garoafelor. Dacă sunt mai multe vaze decât buchete de flori, atunci excesul va rămâne gol. O vază poate conține doar un buchet de flori. Fiecare vază are o caracteristică distinctă (la fel ca și florile). Prin urmare, punerea unui buchet de flori într-o vază are ca rezultat o anumită valoare estetică, exprimată printr-un număr întreg. Valorile estetice sunt prezentate într-un tabel, după cum se arată mai jos. O vază goală are o valoare estetică egală cu 0.

Conform tabelului, azaleele ar arăta grozav în vaza 2, dar ar arăta groaznic în vaza 4.

Cerința

Pentru a obține cel mai plăcut efect trebuie să maximizezi suma valorilor estetice pentru aranjament, păstrând în același timp ordinea necesară a florilor. Dacă există mai multe aranjamente de valoare maximă totală, oricare dintre ele va fi acceptată. Trebuie să afișați exact un aranjament.

Date de intrare

Fișierul de intrare flowers.in conține pe prima linie numerele F V. Următoarele F linii conțin câte V numere întregi, astfel încât Aij este dat ca al j-lea număr de pe a (i+1)-a linie.

Date de ieșire

Fișierul de ieșire flowers.out va conține pe prima linie suma maximă a valorilor estetice pentru aranjament. A doua linie conține aranjamentul ca un șir de F numere astfel încât al k-lea număr din șir să identifice vaza în care este pus buchetul k.

Restricții și precizări

• 1 ≤ F ≤ 100, unde F este numărul de buchete de flori. Buchetele sunt numerotate de la 1 la F
• F ≤ V ≤ 100 unde V este numărul de vaze
• -50 ≤ Aij ≤ 50 unde Aij este valoarea estetică obținută punând buchetul de flori i în vaza j

Exemplu:

flowers.in

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

flowers.out

53 
2 4 5