gradina

Păcală a reușit să ducă la bun sfârșit înțelegerea cu boierul căruia-i fusese slugă și, conform învoielii, boierul trebuie să-l răsplătească dându-i o parte din livada sa cu pomi fructiferi.

Boierul este un om foarte ordonat, așa că livada sa este un pătrat cu latura de $N$ metri unde, pe vremuri, fuseseră plantate $N$ rânduri cu câte $N$ pomi fiecare. Orice pom fructifer putea fi identificat cunoscând numărul rândului pe care se află și poziția sa în cadrul rândului respectiv. Cu timpul, unii pomi s-au uscat şi acum mai sunt doar $P$ pomi. Păcală trebuie să-și delimiteze în livadă o grădină pătrată cu latura de $K$ metri.

Cerință

Cunoscând dimensiunile livezii și grădinii, numărul pomilor din livadă și poziția fiecăruia, determinați numărul maxim de pomi dintr-o grădină pătrată de latură $K$ și numărul modurilor în care poate fi amplasată grădina cu numărul maxim de pomi.

Date de intrare

Fișierul gradina.in conține:

• pe prima linie numerele naturale $N, P$ și $K$, separate prin câte un spațiu, cu semnificaţia din enunţ;
• pe următoarele $P$ linii câte $2$ numere naturale $L$ și $C$, separate printr-un spațiu, reprezentând numărul rândului, respectiv poziția în rând a fiecărui pom din livadă.

Date de ieșire

Fișierul gradina.out va conține:

• pe prima linie numărul maxim de pomi fructiferi dintr-o grădină pătrată cu latura de $K$ metri;
• pe a doua linie numărul de posibilități de a amplasa grădina astfel încât să conțină numărul maxim de pomi determinat.

Restricții și precizări

• $2 \leq N \leq 1 \ 000$
• $1 \leq P \leq N^2$
• $1 \leq K \leq N$

Exemplu

gradina.in

12 10 5
4 3
5 5
6 8
7 3
7 7
8 8
9 3
9 6
10 10
10 5

gradina.out

5
8

Explicație

Grădina lui Păcală poate avea maximum $5$ pomi fructiferi.

Ea poate fi amplasată în $8$ moduri, având colțul stânga-sus de coordonate: $(5, 3)$, $(5, 4)$, $(5, 5)$, $(6, 3)$, $(6, 4)$, $(6, 5)$, $(6, 6)$, $(7, 3)$.