==Include(page="template/taskheader" task_id="parcele")==
 
==Include(page="template/raw")==
 
Parcele
 
 
 
Pe o campie intinsa se afla N copaci situati in puncte de coordonate intregi. Fermierul Ion doreste sa cumpere cateva parcele pe acea campie. Ion poate cumpara numai parcele de forma dreptunghiulara, cu laturile paralele cu axele de coordonate de pe harta zonei, cu dimensiunile intregi fixate (DX pentru axa OX si DY pentru axa OY) si avand colturile situate in puncte de coordonate intregi. Cumpararea unei parcele va trece in proprietatea lui Ion interiorul ei (se considera ca laturile parcelei fac parte din interior).
 
Numarandu-si banii, Ion s-a hotarat sa cumpere exact DOUA parcele care, evident, sa nu aiba nici un punct comun. Deoarece lui Ion ii plac foarte mult copacii, el isi va alege o modalitate de amplasare a celor doua parcele astfel incat in interiorul lor (inclusiv pe laturi) sa se afle cat mai multi copaci. In acest scop, Ion va cere ajutorul.
 
h2. Cerinta
 
Scrieti un program care sa determine o modalitate de amplasare a parcelelor, astfel incat Ion sa detina cat mai multi copaci!
 
h2. Date de Intrare
 
Fisierul de intrare parcele.in contine:
 
- pe prima linie doua numere intregi DX si DY, reprezentand dimensiunile unei parcele;
 
- pe cea de a doua linie un numar intreg N, reprezentand numarul de copaci;
 
- pe fiecare dintre urmatoarele N linii cate doua numere intregi X[i] si Y[i], reprezentand coordonatele copacului cu numarul i.
 
h2. Date de Iesire
 
In fisierul de iesire parcele.out veti afisa pe prima linie numarul maxim de copaci pe care ii poate detine Ion.
 
h2. Restrictii
 
S 1 -L- DX, DY -L- 99.999
 
S 1 -L- N -L- 100.000
 
S coordonatele copacilor sunt numere intregi intre 0 si 99999 inclusiv
 
S nu exista doi copaci situati in acelasi punct
 
S parcelele pot fi plasate oriunde, cu conditia ca sa nu se intersecteze
 
h2. Exemplu
 
parcele.in parcele.out Explicatie
2 1 6 O solutie posibila este:
 
7 - prima parcela are colturile (-1, 0) si (1, 1)
 
0 0 - a doua parcela are colturile (3, 0) si (5, 1)
 
1 0
 
1 1
 
3 0
 
3 1
 
4 0
 
1000 1000
 

==Include(page="template/taskheader" task_id="parcele")==
 
Pe o campie intinsa se afla $N$ copaci situati in puncte de coordonate intregi. Fermierul Ion doreste sa cumpere cateva parcele pe acea campie. Ion poate cumpara numai parcele de forma dreptunghiulara, cu laturile paralele cu axele de coordonate de pe harta zonei, cu dimensiunile intregi fixate ({$DX$} pentru axa $OX$ si $DY$ pentru axa $OY$) si avand colturile situate in puncte de coordonate intregi. Cumpararea unei parcele va trece in proprietatea lui Ion interiorul ei (se considera ca laturile parcelei fac parte din interior).
Numarandu-si banii, Ion s-a hotarat sa cumpere exact DOUA parcele care, evident, sa nu aiba nici un punct comun. Deoarece lui Ion ii plac foarte mult copacii, el isi va alege o modalitate de amplasare a celor doua parcele astfel incat in interiorul lor (inclusiv pe laturi) sa se afle cat mai multi copaci. In acest scop, Ion va cere ajutorul.
 
h2. Cerinta
 
Scrieti un program care sa determine o modalitate de amplasare a parcelelor, astfel incat Ion sa detina cat mai multi copaci!
 
h2. Date de intrare
 
Fisierul de intrare $parcele.in$ contine:
- pe prima linie doua numere intregi $DX$ si $DY$, reprezentand dimensiunile unei parcele;
- pe cea de a doua linie un numar intreg $N$, reprezentand numarul de copaci;
- pe fiecare dintre urmatoarele $N$ linii cate doua numere intregi $X{~i~}$ si $Y{~i~}$, reprezentand coordonatele copacului cu numarul $i$.
 
h2. Date de iesire
 
In fisierul de iesire $parcele.out$ veti afisa pe prima linie numarul maxim de copaci pe care ii poate detine Ion.
 
h2. Restrictii
 
* $1 ≤ DX, DY ≤ 99.999$
* $1 ≤ N ≤ 100.000$
* coordonatele copacilor sunt numere intregi intre $0$ si $99999$ inclusiv
* nu exista doi copaci situati in acelasi punct
* parcelele pot fi plasate oriunde, cu conditia ca sa nu se intersecteze
 
h2. Exemplu
 
 
table(example). |_. parcele.in |_. parcele.out |
| 2 1
7
0 0
1 0
1 1
3 0
3 1
4 0
1000 1000
| 6 |
 
h3. Explicatii
 
O solutie posibila este: prima parcela are colturile $(-1, 0)$ si $(1, 1)$ iar a doua parcela are colturile $(3, 0)$ si $(5, 1)$
 
 
==Include(page="template/taskfooter" task_id="parcele")==

==Include(page="template/taskfooter" task_id="parcele")==

466