civilizatie

În vremuri străvechi Pământul era locuit de către o civilizaţie neobişnuită condusă după reguli matematice foarte riguroase. Această civilizaţie era formată din mai multe oraşe-stat asemeni oraşelor antice. Fiecare oraş s-a dezvoltat treptat pornind de la un singur cartier de formă pătrată cu suprafaţa de un hectar, în jurul căruia se adăugau în fiecare an cartiere de câte un hectar fiecare în felul următor:

• în primul an s-a format cartierul iniţial,
• în al doilea an oraşul s-a extins formând $4$ noi cartiere în toate cele patru puncte cardinale,
• în anul următor oraşul s-a extins cu $8$ noi cartiere dispuse în jurul cartierelor deja formate, şi aşa mai departe, în fiecare an oraşul extinzându-se cu încă un rând de cartiere.

Primul an	Al doilea an	Al treilea an	Al patrulea an	Al cincilea an

Extinderea unui oraş se opreşte când întâlnește un alt oraş sau dacă, deşi nu a întâlnit încă un alt oraş, ajunge la marginea hărţii pe oricare dintre cele patru puncte cardinale. Două oraşe se întâlnesc când suprafeţele ocupate de ele ajung să se atingă sau între cartierele marginale ale celor două orașe se mai află doar un hectar.

Situaţii în care suprafeţele orașelor se ating	Situaţii în care între suprafeţele orașelor există un spaţiu de un hectar

Cerință

1. Dimensiunea suprafeţei (în hectare) pe care ar ocupa-o după $t$ ani, dacă nu ar întâlni nici un alt oraş şi nici nu ar ajunge la marginea hărţii.
2. Timpul scurs până când toate cele $N$ oraşe şi-au încetat extinderea, începută din cartierele iniţiale ale căror coordonate se citesc din fişier, şi aria suprafeţei din hartă rămasă neocupată, exprimată în hectare.

Date de intrare

Fişierul de intrare civilizatie.in conţine pe prima linie un număr natural $p$. Pentru toate testele de intrare, p poate avea doar valoarea $1$ sau valoarea $2$.

A doua linie a fişierului conţine două numere naturale $x$ și $y$ reprezentând dimensiunile hărţii.

A treia linie a fişierului conţine numărul natural $t$.

A patra linie a fişierului conţine numărul natural $N$.

Pe următoarele N linii se găsesc câte două numere $i$ și $j$ reprezentând coordonatele iniţiale ale celor $N$ oraşe.

Date de ieșire

Dacă valoarea lui p este 1, atunci se va rezolva numai prima cerință.

În acest caz, în fişierul de ieşire civilizatie.out se va scrie un singur număr natural, reprezentând aria suprafeţei (în hectare) unui oraş după t ani, dacă nu ar întâlni nici un alt oraş şi nici nu ar ajunge la marginea hărţii.
Dacă valoarea lui p este 2 atunci, se va rezolva numai a doua cerință.

În acest caz, fişierul de ieşire va conține pe prima linie un număr natural reprezentând aria suprafeţei din hartă rămasă neocupată după ce toate cele N oraşe şi-au încetat expansiunea, iar pe a doua linie un număr natural reprezentând timpul scurs până când ultimul oraş s-a oprit din expansiune.

Restricții și precizări

• $1 \leq N \leq 2 \ 000$
• $1 \leq x, y, t \leq 100 \ 000$
• Pentru $30$% din teste se garantează faptul că $x, y \leq 500$
• Pentru rezolvarea corectă a primei cerinţe se acordă $20$ de puncte, iar pentru rezolvarea corectă a celei de-a doua cerințe se acordă $80$ de puncte.

Exemplul 1

civilizatie.in

1
7 9
9
2
3 2 
4 6

civilizatie.out

145

Explicație

$p = 1$, în fişier se va scrie aria suprafeței ce ar putea fi ocupată de un oraş în timp de $9$ ani.

Atenție! Pentru acest test se rezolvă doar cerința 1).

Exemplul 2

civilizatie.in

2
7 9
5
2
3 2
4 6

civilizatie.out

33
4

Exemplul 3

civilizatie.in

2
10 10
5
3
2 2
2 4
3 2

civilizatie.out

97
1

Explicație

$p=2$, deci se rezolvă doar cerința 2

În acest caz, cele $3$ civilizații nu se vor putea extinde deloc, deci celelalte $97$ de hectare rămân neocupate.