Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

ˇ a

Slovak University of Technology

Pavol Jozef Saf´rik University in Koˇice

s

ˇ

University of Zilina

Masaryk University

Matej Bel University in Bansk´ Bystrica

a

University of West Bohemia

CTU Open Contest 2016

Orchard Division

orchard.c, orchard.cpp, orchard.c11, Orchard.java, orchard.py

Uncle Oliver is going to sell a significant part of his famous dwarf plum tree orchard. He is going

to divide the orchard into two parts, sell the first one and keep the other one.

The trees were originally planted in regular rows and columns forming a rectangular grid with

the same number of rows and columns. As years went by, Oliver removed many trees which

were weak or plagued by bugs so nowadays there is also a lot of free squares unoccupied by any

tree.

Oliver has decided that he will keep exactly half of all the trees in the orchard. Moreover, he

has few additional demands which, in his opinion, will ensure easy maintenance of his part in

the future.

· The part Oliver is going to keep should be in the shape of a rectangle.

· A least one corner of the rectangle should coincide with a corner of the orchard.

· The rectangle area should be as small as possible.

Originally, each tree was planted in the center of an imaginary square whose area was exactly

one square meter. Thus, the position of each tree can be described by the coordinates of the

square on which it is standing. The dividing fence between the two parts of the orchard will run

along the borders of the squares.

Input Specification

There are more test cases. Each case starts with a line containing two integers M (1 ≤ M ≤ 109)

and N (1 ≤ N ≤ 106 ) separated by space. The orchard side length in meters is expressed by

M and the number of trees in the orchard is expressed by N . Next, there are N lines, each

line specifies x and y coordinates of one tree in the orchard. The coordinates are separated by

space. For simplicity reasons, we assume that the coordinates are zero based, so the coordinates

of the squares in the corners of the orchard are (0, 0), (0, M - 1), (M - 1, M - 1), (M - 1, 0). All

coordinate pairs (x, y) in one test case are unique.

Output Specification

For each test case, print a single line with one whole number A denoting the minimum possible

area in square meters of uncle Oliver's part of the orchard. If it is not possible to divide the

orchard according to Oliver's demands print "-1". Note that the output value might not fit into

32-bit integer type.

Sample Input

6

8

4

5

1

4

0

3

5

3

1

2

3

2

3

1

2

0

3

3

2

0

1

1

0

2

2

2

0

0

1

1

Output for Sample Input

12

-1

1