Colaj

La etapa finală a Concursului pe Echipe al Micilor Artişti, pe primul loc s-au clasat două echipe $A$ şi $B$, cu acelaşi punctaj. Comisia de Evaluare, pentru a le departaja, a introdus o nouă probă de baraj care vizează atât talentul copiilor, cât şi isteţimea lor.

Astfel, echipa $A$ trebuie să realizeze un colaj alb-negru având la dispoziţie o planşă dreptunghiulară de culoare albă şi n dreptunghiuri de culoare neagră. Membrii acestei echipe vor trebui să lipească pe planşă toate dreptunghiurile, cu laturile paralele cu laturile planşei. Pot exista şi dreptunghiuri lipite în interiorul altui dreptunghi, sau dreptunghiuri care se intersectează, sau dreptunghiuri cu laturi pe laturile planşei, precum şi suprafeţe din planşă neacoperite cu dreptunghiuri.

După ce aşează toate dreptunghiurile, membrii echipei $A$ trebuie să comunice echipei $B$ numărul $n$ de dreptunghiuri negre primite, lungimea m a laturii orizontale a planşei, lungimea $p$ a laturii verticale a planşei, şi coordonatele vârfurilor din stânga-jos şi dreapta-sus ale fiecărui dreptunghi de pe planşă (coordonate referitoare la reperul cartezian $xOy$ cu originea $O$ în colţul din stânga-jos a planşei şi cu axa de coordonate $Ox$, respectiv $Oy$, pe dreapta suport a laturii orizontale, respectiv a laturii verticale a planşei).

Pentru a câştiga concursul, echipa $B$ trebuie să ghicească numărul zonelor continue maximale de culoare albă, conţinute de colajul realizat de echipa $A$. O zonă albă este considerată continuă dacă oricare ar fi două puncte $P, Q$ din zona respectivă, se poate uni punctul $P$ de punctul $Q$ printr-o linie dreaptă sau frântă care să nu intersecteze interiorul nici unui dreptunghi negru. O zonă albă continuă este considerată maximală dacă nu există o altă zonă albă continuă de arie mai mare care să includă zona respectivă.

Cerinţă

Scrieţi un program care să citească numărul n al dreptunghiurilor negre primite de echipa $A$, lungimile $m$ şi $p$ ale laturilor planşei, coordonatele vârfurilor din stânga-jos şi dreapta-sus ale fiecărui dreptunghi negru primit, şi care să determine numărul zonelor continue maximale de culoare albă existente în colajul realizat de echipa $A$.

Date de intrare

Fişierul de intrare colaj.in conţine:

• pe prima linie, o valoare naturală $n$, reprezentând numărul de dreptunghiuri negre date echipei $A$
• pe a doua linie, $2$ numere naturale, separate prin spaţiu, reprezentând lungimile laturilor planşei
• următoarele $n$ linii conţin câte patru numere naturale, separate prin câte un spaţiu, care reprezintă coordonatele $(a_1,b_1)$ şi $(c_1,d_1)$ ale vârfurilor din stânga-jos şi dreapta-sus ale primului dreptunghi,..., coordonatele $(a_n,b_n)$ şi $(c_n,d_n)$ ale vârfurilor din stânga-jos şi dreapta-sus ale celui de-al $n$-lea dreptunghi.

Date de ieșire

Fişierul de ieşire colaj.out va conţine o singură linie pe care se va scrie un singur număr natural reprezentând numărul zonelor continue maximale de culoare albă, conţinute de colaj.

Restricții și precizări

• $1 \leq n \leq 100$
• $a_1 < c_1 \leq m, \ a_2 < c_2 \leq m, ..., \ a_n < c_n \leq m$
• $b_1 < d_1 \leq p, \ b_2 < d_2 \leq p, ..., \ b_n < d_n \leq p$
• Toate coordonatele vârfurilor dreptunghiurilor şi lungimile laturilor planşei sunt numere naturale, $0<m,p<8 \ 000$
• Dacă $(x,y)$ şi $(z,t)$ sunt coordonatele a două vârfuri din două dreptunghiuri distincte, atunci: $x≠z$ şi $y≠t$.
• În $40\%$ din teste: $n < 30, m \leq 180, p \leq 180$
• în $40\%$ din teste: $70 \leq n \leq 100, 180 < p < 1 \ 000, 180 < m < 1 \ 000$
• în $20\%$ din teste: $50 < n < 80, 7 \ 000 < m < 8 \ 000, 7 \ 000 < p < 8 \ 000$

Exemplu

colaj.in

7
17 16
1 1 10 5
2 6 8 8
0 9 17 15
3 2 4 11
5 3 6 12
7 4 12 13
14 10 16 14

colaj.out

6

Explicație

$n=7, m=17, p=16.$
Sunt $7$ dreptunghiuri negre.
Colajul realizat de echipa $A$ este cel din desenul alăturat. Se observă $6$ zone continue maximale de culoare albă conţinute de colaj (cele numerotate în figura alăturată).