유라시아 합중국

서기 5013년, 유라시아 대륙을 정복한 황제가 유라시아 합중국을 세웠다. 합중국은 대륙 전체를 차지할 만큼 넓고 인구가 많아서, 황제는 영토를 지방으로 나누어 효율적으로 관리하려고 한다. 합중국에는 주택이 $N$채 있고, $i$번째 주택은 2차원 유클리드 좌표평면의 $(x_i, y_i)$에 있다. 황제는 다음 조건을 만족하도록 주택을 지방에 나누어 맡긴다.

• 조건 1. 각 지방은 $x$좌표가 일정한 구간 안에 들어오는 주택을 관리한다. 이때 어떤 지방이 모든 주택을 관리하거나, 어떤 주택도 관리하지 않을 수 있다.
• 조건 2. 모든 주택은 정확히 한 지방이 관리해야 한다.
• 조건 3. 지방은 최대 $K$개까지 만들 수 있다.

유라시아 대륙에는 인종, 종교, 민족이 다양하다. 이들 사이의 분쟁을 막으려면 각 지방의 분열을 최대한 줄여야 한다. 어떤 지방의 분열도는 그 지방이 관리하는 주택 중 가장 멀리 떨어진 두 주택 사이의 거리이다. 거리는 유클리드 거리로 잰다. 황제를 도와서 각 지방의 분열도 중 최댓값을 최소로 만들어라.

첫째 줄에 주택의 개수 $N$과 지방의 개수 $K$가 공백으로 구분되어 주어진다.

다음 $N$개 줄 중 $i$번째 줄에는 두 정수 $x_i$, $y_i$가 공백으로 구분되어 주어진다. $(x_i, y_i)$ 위치에 주택이 있다는 뜻이다.

각 지방의 분열도 중 최댓값이 가장 작아지도록 나누었을 때 그 최댓값을 $M$이라고 하자. $M^2$을 출력한다. 좌표가 모두 정수이므로 $M^2$도 항상 정수이다.

• $1 \le K \le N \le 250\,000$
• 모든 주택의 좌표는 서로 다르다. 즉 $i \ne j$이면 $x_i \ne x_j$이거나 $y_i \ne y_j$이다.
• $0 \le x_i, y_i \le 10^9$