placa

Un gard este format din mai multe plăci dreptunghiulare. Fiecare placă este, la rândul ei, construită din $N \times M$ cărămizi. Una dintre plăci ridică o problemă, deoarece este deteriorată. Placa este reprezentată pe hârtie cu ajutorul unei matrice cu $N$ linii și $M$ coloane, numerotate de la $1$ la $N$, respectiv de la $1$ la $M$. Matricea conține doar valori $0$ și $1$, și respectă următoarele reguli:

• un element egal cu $1$ indică prezența în aceea poziție a unei cărămizi, iar un element egal cu $0$ indică absența ei
• linia $1$ și linia $N$ conțin numai valori egale cu $1$, pentru că marginea de sus și cea de jos a plăcii este intactă;
• din orice element egal cu $1$, situat în interiorul matricei, se poate ajunge pe linia $1$ sau pe linia $N$ sau pe amândouă, mergând doar în sus sau doar în jos, parcurgând numai valorile egale cu $1$
• există cel puțin o coloană stabilă (formată numai din elemente egale cu $1$).

Se dorește modificarea plăcii și pentru aceasta se pot șterge din matrice maximum $K$ coloane alăturate. După ștergere se alipesc coloanele rămase și se deplasează pe verticală partea de sus a plăcii spre cea de jos, până când se va forma o coloană stabilă.

Cerinţă

Să se determine înălțimea minimă $\text{Hmin}$ pe care o poate avea placa ștergând cel mult $K$ coloane alăturate. Identificați numărul minim de coloane alăturate care trebuie șterse pentru a obține înălțimea $\text{Hmin}$.

Date de intrare

Din fișierul de intrare placa.in se citesc de pe prima linie $3$ numere naturale $N$, $M$, $K$ separate prin câte un spațiu, având semnificația din enunț. Pe fiecare dintre următoarele $M$ linii ale fișierului se găsesc perechi de numere naturale $N_1, N_2$, separate printr-un spațiu. Astfel pe linia $i + 1$ a fișierului de intrare numărul $N_1$ reprezintă numărul de elemente de $1$ situate pe coloana $i$, începând cu linia $1$, deplasându-ne în „jos” până la întâlnirea unei valori egale cu $0$, sau până se ajunge pe linia $N$; numărul $N_2$ reprezintă numărul de elemente de $1$ situate pe coloana $i$, începând cu linia $N$, deplasândune în „sus” până la întâlnirea unei valori egale cu $0$, sau până se ajunge pe linia $1$

Date de ieșire

În fișierul de ieșire placa.out se va scrie pe prima linie înălțimea minimă cerută $\text{Hmin}$, iar pe a doua linie numărul minim de coloane ce trebuie eliminate pentru a obține înălțimea $\text{Hmin}$.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $1 \leq M \leq 100 \ 000$
• $1 \leq K \lt M$
• se garantează că pe liniile ce conțin informații referitoare la cele $M$ coloane ale matricei există cel puțin o linie pe care se află valoarea $N$ de $2$ ori, în rest suma celor două valori este strict mai mică decât $N$
• toate valorile din fișier sunt strict pozitive
• se acordă $30\%$ din punctajul pe test dacă doar prima valoare e corectă și $70\%$ din punctajul pe test dacă doar a doua valoare e corectă

Exemplu

placa.in

5 6 3
1 1
2 1
1 2
5 5
1 3
1 1

placa.out

3
2

Explicație

Matricea inițială:
$1 \ 1 \ 1 \ 1 \ 1 \ 1$
$0 \ 1 \ 0 \ 1 \ 0 \ 0$
$0 \ 0 \ 0 \ 1 \ 1 \ 0$
$0 \ 0 \ 1 \ 1 \ 1 \ 0$
$1 \ 1 \ 1 \ 1 \ 1 \ 1$
Înălțimea minimă este $3$ și se poate obține eliminând, de exemplu, coloanele $3, 4, 5$ rezultând matricea:
$1 \ 1 \ 1$
$0 \ 1 \ 0$
$1 \ 1 \ 1$
O altă modalitate de a obține aceeași înălțime dar prin ștergerea unui număr minim de coloane ($4$ și $5$) conduce la:
$1 \ 1 \ 1 \ 1$
$0 \ 1 \ 1 \ 0$
$1 \ 1 \ 1 \ 1$