== include(page="template/taskheader" task_id="betasah") ==
Jocul betasah se joaca folosindu-se doar piese asemanatoare damelor clasicului sah, numite tot dame. Suprafata de joc are o forma triunghiulara si este formata din $N(N+1)/2$ patrate identice dispuse pe $N$ randuri si $N$ coloane. Randurile se numeroteaza de sus in jos, de la $1$ la $N$. Coloanele se numeroteaza de la stanga la dreapta, de la $1$ la $N$. Primul rand contine un singur patrat, al doilea rand contine doua patrate alaturate, ..., al $N$-lea rand contine $N$ patrate alaturate, ca in suprafetele de joc cu $N=6$ din figurile de mai jos. Din cele $N(N+1)/2$ patrate, $K$ sunt gri, iar restul sunt albe. Pozitia fiecarui patrat de pe suprafata de joc este data de randul si coloana in care acesta este situat.

!problema/betasah?betasah1.jpg!

Pe suprafata de joc sunt asezate $D$ dame in $D$ patrate albe distincte, ocupandu-le. Intr-un patrat alb poate fi asezata o singura dama, iar intr-un patrat gri nu poate fi asezata nicio dama. Pozitia unei dame pe suprafata de joc este data de pozitia patratului alb in care este asezata dama.
Damele pot accesa orice patrat alb neocupat situat pe directiile: verticala, orizontala sau diagonala, numerotate de la $1$ la $8$ in figura $b)$. Accesul pe o directie se face trecand din patrat alb in patrat alb (doar patrate albe neocupate) pana la intalnirea unui patrat gri sau a unui patrat alb ocupat de o alta dama sau pana la terminarea suprafetei de joc.
Numim patrat accesibil orice patrat alb neocupat (de pe suprafata de joc) care ar putea fi accesat de cel putin una din cele $D$ dame.
De exemplu, pentru suprafata de joc din figura $c)$ numarul de patrate accesibile (marcate cu $X$) de pe suprafata este $11$; pentru suprafata de joc cu $N=6$, $D=3$ si $K=4$ din figura $d)$ numarul de patrate accesibile de pe suprafata este $13$. In figura $e)$ sunt marcate cu $X$ patratele accesibile fiecarei dame de pe suprafata de joc din figura $d)$.

!problema/betasah?betasah2.jpg!
 

h2. Cerinta
Scrieti un program care sa citeasca numerele naturale $N D K$, pozitiile damelor si ale patratelor gri pe suprafata de joc si care sa determine:

h2. Date de intrare

Fisierul de intrare $betasah.in$ contine:
 
* pe prima linie cele trei numere naturale $N D K$, separate prin cate un spatiu, cu semnificatia din enunt;
 
* pe linia $i+1$ doua numere naturale nenule $x{~i~} y{~i~}$, separate prin cate un spatiu, reprezentand pozitia damei $i$ pe suprafata de joc (randul $x{~i~}$ si coloana $y{~i~}$), pentru $i=1,2,3,...,D$;
 
* pe linia $D+1+j$ doua numere naturale nenule $z{~j~} t{~j~}$, separate printr-un singur spatiu, reprezentand pozitia patratului gri $j$ pe suprafata de joc (randul $x{~i~}$ si coloana $y{~i~}$), pentru $j=1,2,3,...,K$.
 

h2. Date de ieşire

În fişierul de ieşire $betasah.out$ ...

Fisierul de iesire $betasah.out$ va contine pe prima linie numarul natural $M$  si pe a doua linie numarul natural $P$, cu semnificatia din enunt.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 1000$
 
* $1 ≤ D ≤ 100$
 
* $1 ≤ K ≤ 50$
 
* $D + K ≤ N(N+1)/2$
 
* $1 ≤ y{~i~} ≤ x{~i~} ≤ N$ pentru $i=1,2,3,...,D$
 
* $1 ≤ t{~j~} ≤ z{~j~} ≤ N$ pentru $k=1,2,3,...,K$
 
* numarul $M$ se va scrie obligatoriu pe prima linie a fisierului de iesire $betasah.in$.
 
* numarul $P$ se va scrie obligatoriu pe a doua linie a fisierului de iesire $betasah.out$.
 
* pentru rezolvarea corecta a cerintei $1)$ se acorda $20%$ din punctaj, iar pentru rezolvarea corecta a cerintei $2)$ se acorda $80%$ din punctaj.

h2. Exemplu
table(example). |_. betasah.in |_. betasah.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6 3 4
  3 2
  5 2
  5 4
  3 1
  4 3
  6 4
  1 1
| 5
  13

|
h3. Explicaţie

...

$N=6$, $D=3$, $K=4$.
Randurile $5$ si $6$ contin numarul maxim $M=5$ de patrate albe.
Numarul de patrate accesibile de pe suprafata de joc este $P=13$.
In desenul alaturat corespunzator suprafetei date, cele $13$ patrate accesibile sunt marcate cu $X$.
Astfel, pe prima linie a fisierului $betasah.out$ se va scrie numarul $5$, iar pe a doua linie a fisierului se va scrie numarul $13$.
 
!problema/betasah?betasah3.jpg!

== include(page="template/taskfooter" task_id="betasah") ==

9942