데카르트

데카르트 왕국은 좌표 $(x, y)$가 정해진 평면 위에 있다. 왕국은 사방으로 무한히 뻗어 있다고 본다.

왕은 새 궁전을 짓고자 한다. 궁전은 좌표축에 평행한 변을 가진 정사각형이다. 궁전은 얼마든지 커도 되지만, 왕은 안전을 더 걱정한다.

왕국에는 $n$개의 경비 초소가 있으며, $i$번째 초소는 $(x_i, y_i)$에 있다. 왕은 여러 경비 조를 편성해 궁전의 경계를 순찰하게 할 수 있다. 경비병은 비교적 단순한 지시만 따를 수 있다. 각 조에는 서로 다른 초소 정확히 두 개를 배정해야 한다. 조는 그 두 초소를 포함하는 최소 크기의 좌표축 평행 직사각형을 순찰한다. 두 초소의 $x$ 좌표나 $y$ 좌표가 같으면 직사각형의 넓이는 0이 된다. 혼동과 충돌을 막기 위해 각 초소는 최대 한 조에만 배정할 수 있다.

왕은 충분한 안전을 느끼려고 정확히 $k$개의 경비 조를 편성하려 한다. 궁전은 각 조가 순찰하는 직사각형 안에 있어야 한다. 즉, 궁전의 모든 점이 순찰하는 각 직사각형의 내부 또는 경계에 포함되어야 한다. 이 조건을 만족하며 지을 수 있는 궁전의 한 변 길이 중 최댓값을 구하라.

첫 줄에 두 정수 $n$과 $k$가 주어진다 ($2 \le n \le 50000$, $1 \le k \le n/2$). 각각 초소의 수와 필요한 조의 수이다.

이어지는 $n$개의 줄에는 각각 두 정수 $x_i$와 $y_i$가 주어진다 ($-10^6 \le x_i, y_i \le 10^6$). 초소의 좌표이다.

서로 다른 두 초소가 같은 점에 있지 않음이 보장된다.

가능한 궁전의 한 변 길이의 최댓값을 한 개의 수로 출력하라. 안전 조건을 만족하는 넓이가 0이 아닌 궁전이 없으면 $0$을 출력하라.

그림은 처음 두 예제에서 궁전과 경비 경로의 배치를 보여준다. 세 번째 예제에서는 가능한 경로가 선분 하나뿐이므로 한 변의 길이가 0이 아닌 궁전을 만들 수 없다.