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 gradina1.in conţine pe prima linie numerele naturale N P K, separate prin câte un spaţiu, cu semnificaţia din enunţ. Pe următoarele P linii se află câte 2 numere naturale Lin şi Col, 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 gradina1.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 va fi scris numărul de posibilităţi de a amplasa grădina astfel încât să conţină numărul maxim de pomi determinat.

Restricţii

• 2 ≤ N ≤ 1000
• 1 ≤ P ≤ N2
• 1 ≤ K ≤ N

Exemple

gradina1.in	gradina1.out	Explicaţii
12 10 5 4 3 5 5 6 8 7 3 7 7 8 8 9 3 9 6 10 10 11 5	5 5	Grădina lui Păcală poate avea maximum 5 pomi fructiferi. Ea poate fi amplasată în 5 moduri, având colţul stânga-sus de coordonate: (5, 3), (5, 4), (5, 5), (6, 6), (7, 3).

autor: Prof. Alin Burţa

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com