Drag

Cerință

Se dǎ o matrice cu $0$ și $1$. Considerăm că avem $0$ în celulele libere și $1$ în celulele ocupate. Dorim să completăm cu $1$ cât mai multe linii consecutive din partea de jos a matricei (adică să fie complete linia $n$, linia $n-1$, $\dots$). Dispunem de operația: selectăm o celulă egală cu $1$ și apoi o putem trage la stânga, la dreapta sau în jos până o fixăm unde dorim. O putem trage din poziția curentă în una vecină doar dacă acea poziție este liberǎ. Practic o putem muta în alt loc mai jos (sau pe același rând) mergând prin zone libere. Mutarea la stânga sau la dreapta nu costă nimic, dar mutarea în jos are costul egal cu numărul de rânduri care se coboară.

Să se determine:

1. Numărul maxim de linii care se pot completa jos. Atenție, ne intereseazǎ doar numǎrul de linii pline de 1, cele parțial completate sunt ignorate.
2. Costul minim pentru a completa acest număr maxim de linii.

Date de intrare

Pe prima linie a fișierului de intrare drag.in se aflǎ un număr $C$ reprezentând cerința de rezolvat și un număr $n$ reprezentând dimensiunea matricei (care este una pătratică).
Pe fiecare din următoarele $n$ linii se află câte $n$ valori $0$ sau $1$ reprezentând configurația matricei date. Liniile sunt numerotate de sus în jos începând cu 1 iar coloanele sunt numerotate de la stânga la dreapta, de asemenea, începând cu 1. Numerele de pe aceeași linie sunt separate prin spațiu.

Date de ieșire

În fișierul drag.out, se va scrie astfel:

• O valoare, reprezentând numărul maxim de rânduri care se pot completa jos, dacă avem $C = 1$.
• Două valori, separate prin spațiu, reprezentând respectiv: numărul maxim de rânduri care se pot completa jos și costul minim pentru a completa acest număr de rânduri, dacă avem $C = 2$.

Restricții și precizări

• $1 \leq n \leq 1 \ 000$;
• $1 \leq c \leq 2$;
• Pentru $26$ de puncte $C=1$;
• Pentru $74$ de puncte $C=2$;
• Atenție, dacă avem $C = 1$, în fișierul de ieșire scriem doar un număr;

Exemplul 1

drag.in

1 4
1 1 0 1
1 0 0 0
1 0 1 1
1 1 0 1

drag.out

2

Exemplul 2

drag.in

2 4
1 1 0 1
1 0 0 0
1 0 1 1
1 1 0 1

drag.out

2 4

Explicație

• Valoarea $1$ de pe linia a doua, o putem trage o poziție la dreapta și apoi una în jos (se completează cu 1 elementul de pe linia $3$ și coloana $2$). Costul până acum este $1$.
• Valoarea $1$ de pe linia $3$ și coloana $3$ se deplasează o poziție în jos. Astfel, avem completată ultima linie. Costul total este până acum $2$.
• Valoarea $1$ de pe linia $1$ și coloana $4$ se deplasează o poziție la stânga și apoi două în jos, ocupând locul lăsat liber prin mutarea elementului anterior, astfel completându-se și a doua linie de jos. Costul final devenind $4$.