mingiute

Mingiute

Intr-un camin oarecare de la periferia orasului locuieste un adolescent rebel, pe numele sau Matei Mingiuta. Dornic de afirmare, acesta patrunde prin efractie in subsolul cladirii si sustrage intreaga rezerva de dero a caminului cu scopul de a o monetiza pe seama colegilor creduli. Din pacate pentru Mingiuta, mafia turceasca a sesizat rapid lipsa detergentului prin mirosul greu al elevilor barbosi, iar el este cel dintai suspect intrucat, nu de mult, a incercat sa vanda la plic gazonul din fata biroului directorului.

Cladirea caminului este alcatuita din $N$ etaje, fiecare etaj avand $M$ camere. Pentru a scapa de orice urma, Mingiuta imparte prada in primul rand pe etaje, aproximand pentru fiecare etaj un numar de $nr[~i~]$ pliculete de dero. Din pacate pentru el, pe fiecare etaj se afla un paracios care supravegheaza o zona continua de camere pe la mijlocul holului. In acest caz, el poate comercializa pliculetele doar in primele $st[~i~]$ si ultimele $dr[~i~]$ camere ale fiecarui etaj $1 ≤ i ≤ N$, maxim unul pe camera. O alta problema ar fi ca mirosul generat de consumul de dero este extrem de volatil si se ridica la etajele superioare. Astfel, in cazul unei inspectii, daca doua camere aflate una sub alta la etaje diferite au primit pliculete, schema va deveni evidenta si Mingiuta va fi prins. In caz contrar, probabilitatea ca Mingiuta sa fie prins ramane direct proportionala cu diferenta absoluta maxima intra pliculetele distribuite la inceputul holului si cele distribuite la sfarsitul acestuia pentru fiecare etaj in parte. Deci, cu cat maximul dintre diferentele absolute intre numarul de pliculetele distribuite in primele $st[~i~]$ si ultimele $dr[~i~]$ camere este mai mic, cu atat Mingiuta are sanse mai mari sa scape basma curata.

Cladirea caminului este alcatuita din $N$ etaje, fiecare etaj avand $M$ camere. Pentru a scapa de orice urma, Mingiuta imparte prada in primul rand pe etaje, aproximand pentru fiecare etaj un numar de $nr[~i~]$ pliculete de dero. Camerele fiearui etaj sunt numerotate de la 1 la $M$. Din pacate pentru el, pe fiecare etaj se afla un paracios care supravegheaza o zona continua de camere pe la mijlocul holului. In acest caz, el poate comercializa pliculetele doar in primele $st[~i~]$ si ultimele $dr[~i~]$ camere ale fiecarui etaj $1 ≤ i ≤ N$, maxim unul pe camera.
 
O alta problema ar fi ca mirosul generat de consumul de dero este extrem de volatil si se ridica la etajele superioare. Caminul este proiectat in asa fel incat oricare doua camere numerotate la fel sa se afle una sub alta. Astfel, daca se consuma dero in doua camere numerotate la fel, de pe etaje diferite, mirosul va deveni prea puternic si Mingiuta va fi prins.
 
In caz contrar, probabilitatea ca Mingiuta sa fie prins ramane direct proportionala cu diferenta absoluta maxima intra pliculetele distribuite la inceputul holului si cele distribuite la sfarsitul acestuia pentru fiecare etaj in parte. Deci, cu cat maximul dintre diferentele absolute intre numarul de pliculetele distribuite in primele $st[~i~]$ si ultimele $dr[~i~]$ camere este mai mic, cu atat Mingiuta are sanse mai mari sa scape basma curata.

Sa se scrie un program care determina aceasta diferenta absoluta minima pentru a-l ajuta pe Mingiuta sa decida daca isi va asuma riscul sau va consuma singur intreaga cantitate de dero. In cazul in care el nu poate sa distribuie in siguranta prada afisati "$-1$", soarta acestuia fiind pecetluita.

h2. Restricţii

* $1 ≤ N ≤ 214$
* $1 ≤ M ≤ plm$
* $st[~i~] < M-dr[~i~]+1$  pentru oricare $1 &le; i &le; N$
* $1 &le; nr[~i~] &le; plm$
* $Mingiuta este doar o porecla pe care prietenii i-au dat-o dupa forma punctajului la OJI$
* Definind formal cea de-a doua restrictie, pe fiecare coloana a matricei trebuie sa fie distribuit maxim un pliculet de dero

* $1 ≤ N ≤ 200$
* $1 ≤ M ≤ 200$
* $st[~i~] <= M-dr[~i~]$  pentru oricare $1 &le; i &le; N$
* $0 &le; nr[~i~] &le; M$
* Mingiuta este doar o porecla pe care prietenii i-au dat-o dupa forma punctajului la OJI
* Orice asemanare cu personaje reale este pur intamplatoare, autorul a conceput problema dupa ce s-a uitat prea mult la "Breaking Bad"

h2. Exemplu