비트코인 채굴장

비트코인 채굴은 전력을 매우 많이 쓴다. 어느 날 알리와 베티는 각자 채굴장을 하나씩 체라스 시내에 세우기로 했다. 두 사람은 체라스 시장인 시바를 찾아가 부지를 요청했다.

시바는 채굴장을 세울 수 있는 후보 자리가 표시된 격자 지도를 두 사람에게 보여 주었다. 채굴에 전력이 많이 들어가는 만큼, 시바는 동네에 전력 스파이크가 생기지 않도록 두 채굴장을 서로 최대한 멀리 떨어뜨리려고 한다.

후보 자리의 좌표가 모두 주어질 때, 두 자리 사이의 유클리드 거리(직선 거리) 중 가장 큰 값을 구하라. 후보 자리의 좌표는 항상 정수다.

실수를 다루면 작은 오차가 생기기 쉬우므로, 가장 먼 두 자리 사이의 유클리드 거리를 제곱한 값만 출력하면 된다. 두 점 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 유클리드 거리의 제곱은 다음과 같이 정의한다.

$(x_1 - x_2)^2 + (y_1 - y_2)^2$

첫째 줄에 후보 자리의 개수 $N$이 주어진다. ($2 \le N \le 10^6$)

둘째 줄에 좌표의 절댓값이 가질 수 있는 최댓값 $M$이 주어진다. ($2 \le M \le 1500$) 즉 모든 후보 자리의 좌표 $x$와 $y$는 $-M \le x \le M$과 $-M \le y \le M$을 만족한다.

셋째 줄부터 $N$개의 줄에 후보 자리의 좌표 $X_i$와 $Y_i$가 한 줄에 두 정수로 주어진다. 같은 좌표가 여러 번 나올 수 있다.

가장 먼 두 후보 자리 사이의 유클리드 거리의 제곱을 정수 하나로 출력한다.