Vasile este un tanăr programator angajat recent la o firma oarecare din domenul IT. Deoarece câştigă foarte bine el şi-a achiziţionat un teren, de formă dreptunghiulară.
Colţurile dreptunghiului care definesc acest teren au coordonatele , , unde şi sunt numere naturale. Pe acest teren Vasile doreşete să construiască în primul rând o piscină de arie maximă, de formă dreptunghiulară, cu laturile paralele cu cele ale terenului.
Deşi credea ca şi-a îndeplinit visul, Vasile şi-a dat seama că în viaţă nimic nu este atât de uşor deoarece au apărut două restricţii pe care el trebuie să le respecte:
- Deoarece alimentarea cu apă se poate face doar în colţurile dreptunghiului care reprezintă terenul, piscina trebuie sa aibă un punct comun cu unul dintre punctele , , sau .
- Pe teren se află pomi la coordonate întregi cunoscute. Aceştia nu pot face parte din dreptunghiul ce defineşte piscina. Iar Vasile nici nu se gândeşte să taie vreun copac pentru ca îi place aerul curat. Copacii se pot afla însă pe marginea piscinei.
Cerință
Scrieţi un program care determină aria maximă pe care o poate avea piscina respectând restricţiile din enunţ.
Date de intrare
Fişierul de intrare piscina.in
conţine pe prima linie două numere naturale şi ce reprezintă dimensiunile laturilor terenului. Pe următoarea linie se află numărul natural ce preprezintă numărul de copaci care se află pe teren. Următoarele linii conţin câte două numere şi , separate printr-un spaţiu, reprezentând coordonatele fiecărui copac.
Date de ieșire
Fişierul piscina.out
va conţine o singură linie cu un singur număr întreg reprezentând suprafaţa piscinei de arie maximă.
Restricții și precizări
- , iar şi sunt numere întregi
- Valorile sunt distincte
- Valorile sunt distincte
- Pentru teste în valoare de puncte:
- Pentru teste în valoare de puncte:
Exemplul 1
piscina.in
5 7
4
1 2
2 1
3 5
4 6
piscina.out
15
Explicație
O posibilă soluţie, de arie se observă haşurată în desenul alăturat. Soluţia nu este unică, dar nu există o altă soluţie de arie mai mare.