betasah

Jocul betasah se joacă folosindu-se doar piese asemănătoare damelor clasicului șah, numite tot dame. Suprafața de joc are o formă triunghiulară și este formată din $N \cdot (N+1) / 2$ pătrate identice dispuse pe $N$ rânduri și $N$ coloane. Rândurile se numerotează de sus in jos, de la $1$ la $N$. Coloanele se numerotează de la stânga la dreapta, de la $1$ la $N$. Primul rând conține un singur pătrat, al doilea rând conține două pătrate alăturate, $\dots$, al $N$-lea rând conține $N$ pâtrate alăturate, ca în suprafețele de joc cu $N=6$ din figurile de mai jos. Din cele $N \cdot (N+1) / 2$ pătrate, $K$ sunt gri, iar restul sunt albe. Poziția fiecărui pătrat de pe suprafața de joc este dată de rândul și coloana în care acesta este situat.

Pe suprafața de joc sunt așezate $D$ dame în $D$ pătrate albe distincte, ocupându-le. Într-un pătrat alb poate fi așezată o singură damă, iar într-un pătrat gri nu poate fi așezată nicio damă. Poziția unei dame pe suprafața de joc este dată de poziția pătratului alb în care este așezată dama.
Damele pot accesa orice pătrat alb neocupat situat pe direcțiile: verticală, orizontală sau diagonală, numerotate de la $1$ la $8$ în figura $b$). Accesul pe o direcție se face trecând din pătrat alb în pătrat alb (doar pătrate albe neocupate) până la întâlnirea unui pătrat gri sau a unui pătrat alb ocupat de o altă damă sau până la terminarea suprafeței de joc.
Numim pătrat accesibil orice pătrat alb neocupat (de pe suprafața de joc) care ar putea fi accesat de cel puțin una din cele $D$ dame.
De exemplu, pentru suprafața de joc din figura $c$) numărul de pătrate accesibile (marcate cu $X$) de pe suprafață este $11$; pentru suprafața de joc cu $N=6, D=3$ și $K=4$ din figura $d$) numărul de pătrate accesibile de pe suprafață este $13$. În figura $e$) sunt marcate cu $X$ pătratele accesibile fiecărei dame de pe suprafața de joc din figura $d$).

Cerință

Scrieți un program care să citească numerele naturale $N \ D \ K$, pozițiile damelor și ale pătratelor gri pe suprafața de joc și care să determine:

• numărul maxim $M$ de pătrate albe conținute de un rând al suprafeței de joc;
• numărul $P$ de pătrate accesibile de pe suprafața de joc.

Date de intrare

Fișierul de intrare betasah.in conține:

• pe prima linie cele trei numere naturale $N \ D \ K$, separate prin câte un spațiu, cu semnificația din enunț;
• pe linia $i+1$ două numere naturale nenule $x_i \ y_i$, separate prin câte un spațiu, reprezentând poziția damei $i$ pe suprafața de joc (rândul $x_i$ și coloana $y_i$), pentru $i = 1,2,3,\dots,D$;
• pe linia $D+1+j$ două numere naturale nenule $z_j \ t_j$, separate printr-un singur spațiu, reprezentând poziția pătratului gri $j$ pe suprafața de joc (rândul $x_i$ și coloana $y_i$), pentru $j = 1, 2, 3, \dots , K$.

Date de ieșire

Fișierul de ieșire betasah.out va conține pe prima linie numărul natural $M$ și pe a doua linie numărul natural $P$, cu semnificația din enunț. Pentru obținerea punctajelor parțiale, trebuie respectat acest format.

Restricții și precizări

• $2 \leq N \leq 1 \ 000$;
• $1 \leq D \leq 100$;
• $1 \leq K \leq 50$;
• $D + K \leq N \cdot (N+1) / 2$;
• $1 \leq y_i \leq xi \leq N$;
• $1 \leq t_j \leq zj \leq N$;
• pentru rezolvarea corectă a cerinței $1$) se acordă $20\%$ din punctaj, iar pentru rezolvarea corectă a cerinței $2$) se acordă $80\%$ din punctaj.

Exemplu

betasah.in

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

betasah.out

5
13

Explicație

$N=6, D=3, K=4$.
Rândurile $5$ și $6$ conțin numărul maxim $M=5$ de pătrate albe.
Numărul de pătrate accesibile de pe suprafața de joc este $P=13$.
În desenul alăturat corespunzător suprafeței date, cele $13$ pătrate accesibile sunt marcate cu $X$.
Astfel, pe prima linie a fișierului betasah.out se va scrie numarul $5$, iar pe a doua linie a fișierului se va scrie numărul $13$.