Orchard Division

Uncle Oliver is going to sell a large part of his well known dwarf plum tree orchard. He will divide the orchard into two parts, sell one of them and keep the other.

The trees were originally planted in regular rows and columns, forming a square grid with the same number of rows and columns. Over the years Oliver removed many trees that were weak or eaten by bugs, so today there are also many free squares with no tree on them.

Oliver has decided to keep exactly half of all the trees in the orchard. He also set a few more demands that, in his opinion, will make his part easy to maintain later.

• The part Oliver keeps must be a rectangle.
• At least one corner of the rectangle must coincide with a corner of the orchard.
• The area of the rectangle must be as small as possible.

Each tree stands in the center of a square whose area is exactly one square meter, so the position of a tree is given by the coordinates of the square it stands on. The fence between the two parts runs along the borders of the squares.

The input holds several test cases. Each test case starts with a line containing two integers $M$ ($1 \le M \le 10^9$) and $N$ ($1 \le N \le 10^6$) separated by a space. $M$ is the side length of the orchard in meters and $N$ is the number of trees in the orchard. The next $N$ lines each contain the $x$ and $y$ coordinates of one tree, separated by a space. Coordinates are zero based, so the corner squares of the orchard have coordinates $(0, 0)$, $(0, M-1)$, $(M-1, M-1)$, $(M-1, 0)$. Within one test case all coordinate pairs $(x, y)$ are distinct. The input continues until the end of the file.

For each test case, print one line with the whole number $A$, the smallest possible area in square meters of uncle Oliver's part of the orchard. If the orchard cannot be divided so that every demand holds, print -1 instead. The printed value might not fit into a 32-bit integer type.