flori

Pentru primăvara următoare, firma care răspunde de amenajarea spaţiului verde din centrul oraşului Slatina şi-a propus să planteze rânduri de flori dispuse diagonal, formate din parcele având fiecare un anumit număr de flori. Irigarea florilor se realizează cu o pompă care se deplasează în jurul spaţiului verde, începând din colţul din dreapta sus, mergând în sens invers acelor de ceasornic. Rândurile sunt numerotate cu $1$, $2$, $3$, $\dots$ începând din colţul din dreapta sus, respectând sensul de deplasare al pompei. La udarea unui rând de flori se pompează un număr de litri de apă egal cu numărul de flori de pe rândul respectiv.

Debitul apei la sistemul de pompare se poate păstra, poate fi mărit, dar nu poate fi micşorat. Un rând de flori poate fi udat numai dacă are un număr de flori mai mare sau egal cu cel al ultimului rând udat, cu excepţia primului rând ales pentru a fi udat. Orice rând de flori poate fi udat cel mult o dată, la oricare din capetele sale. Apa se opreşte la revenirea în colţul de plecare.

Cerinţă

Fiind dată o matrice cu $n$ linii şi $m$ coloane, în care fiecare element reprezintă numărul de flori dintr-o parcelă, să se determine numărul maxim de flori ce pot fi udate printr-o rotire completă a pompei în jurul spaţiului verde, iar dintre soluţiile determinate, pe cea având număr minim de rânduri cu flori, precum şi numerele de ordine ale rândurilor udate, respectând ordinea în care au fost udate.

Date de intrare

Fişierul de intrare flori.in conţine pe prima linie numerele naturale $n$ şi $m$ reprezentând numărul de linii, respectiv numărul de coloane ale matricei; fiecare din următoarele $n$ linii conţine câte $m$ numere naturale nenule, separate prin câte un spaţiu, reprezentând numărul de flori din fiecare parcelă de pe linia respectivă a matricei.

Date de ieșire

Fişierul de ieşire flori.out va conţine:

• pe prima linie numărul maxim de flori ce pot fi udate;
• pe a doua linie numărul minim de rânduri udate;
• pe a treia linie numerele de ordine ale rândurilor stropite, în ordinea udării lor, separate prin câte un spaţiu.

Restricții și precizări

• $0 < n,m \leq 900$;
• $0$ < numărul de flori dintr-o parcelă $\leq 60 \ 000$
• Pentru prima cerinţă rezolvată corect se obţine $40\%$ din punctaj, pentru primele două cerinţe rezolvate corect se obţine $60\%$ din punctaj.

Exemplu

flori.in

5 6
2 1 3 5 2 3
3 4 5 6 4 3
2 3 6 3 4 9
1 2 7 2 5 1
10 5 14 10 10 3

flori.out

104
7
1 2 4 5 8 7 6

Explicație

La deplasarea pe prima latură orizontală a stratului de flori sunt udate rândurile $1$, $2$, $4$ şi $5$, la deplasarea pe prima latură verticală se udă rândul $8$, iar rândurile $7$ şi $6$ la deplasarea pe latura de jos a stratului.