과수원 분할

올리버 아저씨는 유명한 왜성 자두나무 과수원의 상당 부분을 팔기로 했다. 과수원을 두 부분으로 나눈 다음, 한쪽은 팔고 다른 한쪽은 자기가 갖는다.

나무는 원래 행과 열을 맞춰 심었고, 행의 수와 열의 수가 같은 정사각형 격자를 이룬다. 세월이 흐르는 동안 올리버는 약하거나 벌레가 먹은 나무를 많이 뽑아냈다. 그래서 지금은 나무가 없는 빈 칸도 많다.

올리버는 과수원에 있는 나무 중 정확히 절반을 남기기로 했다. 여기에 더해, 나중에 손질하기 편하도록 조건을 몇 가지 걸었다.

• 올리버가 갖는 부분은 직사각형이어야 한다.
• 직사각형의 꼭짓점 중 적어도 하나는 과수원의 꼭짓점과 겹쳐야 한다.
• 직사각형의 넓이는 가능한 한 작아야 한다.

나무는 저마다 넓이가 정확히 1제곱미터인 정사각형 칸의 한가운데에 심겨 있다. 그래서 나무의 위치는 그 나무가 서 있는 칸의 좌표로 나타낸다. 두 부분을 가르는 울타리는 칸의 경계를 따라 놓인다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 $M$ ($1 \le M \le 10^9$)과 $N$ ($1 \le N \le 10^6$)이 공백으로 구분되어 주어진다. $M$은 과수원 한 변의 길이를 미터 단위로 나타내고, $N$은 과수원에 있는 나무의 수이다. 다음 $N$개의 줄에는 나무 한 그루의 $x$ 좌표와 $y$ 좌표가 공백으로 구분되어 주어진다. 좌표는 0부터 시작하므로 과수원 네 모서리 칸의 좌표는 $(0, 0)$, $(0, M-1)$, $(M-1, M-1)$, $(M-1, 0)$이다. 한 테스트 케이스 안에서 좌표쌍 $(x, y)$는 모두 서로 다르다. 입력은 파일이 끝날 때까지 이어진다.

각 테스트 케이스마다 올리버가 갖는 부분의 최소 넓이 $A$를 제곱미터 단위의 정수로 한 줄에 출력한다. 올리버의 조건을 모두 만족하도록 과수원을 나눌 수 없으면 -1을 출력한다. 출력하는 값은 32비트 정수 범위를 넘을 수 있다.