협곡 지도

협곡은 절벽과 절벽 사이에 깊게 파인 골짜기다. 협곡은 지구에만 있는 지형이 아니다. 화성의 적도를 따라 뻗은 마리네리스 협곡은 미국 본토와 비슷한 크기다.

한 지도 회사가 이런 협곡의 지도를 만든다. 협곡의 윤곽은 평면 위의 단순 다각형으로 나타낸다. 지도의 위쪽이 언제나 북쪽을 가리키도록, 지도는 모두 정사각형이고 네 변이 좌표축과 나란하다. 더 자세히 그리려고 협곡 하나를 여러 장에 나누어 그리기도 하는데, 이렇게 묶은 지도를 지도 세트라고 한다.

지도 세트는 협곡의 넓이 전체를 덮어야 한다. 세트에 든 지도는 협곡에 대한 축척이 모두 같고 인쇄되는 크기도 같다. 그래야 여러 장을 나란히 놓고 견주어 볼 수 있다.

지도 세트에는 지도가 정확히 $k$장 들어간다. 한 장이 덮는 넓이가 작을수록 더 자세히 그릴 수 있으므로, 협곡 전체를 덮으면서 한 장이 덮는 넓이가 가장 작은 지도 세트를 찾아야 한다. 지도는 모두 정사각형이고 협곡에서 덮는 넓이가 서로 같다. 지도끼리 겹쳐도 된다. 넓이는 한 변 길이의 제곱이므로 한 변의 길이만 출력한다.

첫째 줄에 다각형의 꼭짓점 개수 $n$과 지도 세트에 들어가는 정사각형 지도의 장수 $k$가 공백을 사이에 두고 주어진다. ($3 \le n \le 2000$, $1 \le k \le 3$)

다음 $n$개의 줄에 다각형의 꼭짓점 좌표 $x$와 $y$가 순서대로 한 줄에 하나씩 주어진다. ($-20000 \le x, y \le 20000$) 모든 좌표는 정수다. 다각형의 어떤 두 변도 서로 교차하지 않고, 모든 꼭짓점은 서로 다르다. 다각형은 자기 자신에 닿거나 자기 자신을 가로지르지 않는 단순 다각형이고, 넓이는 0보다 크다.

협곡 전체를 덮는 $k$장짜리 지도 세트 중에서 지도 한 변의 길이가 가장 짧을 때, 협곡을 기준으로 잰 그 길이를 출력한다. 소수점 아래 셋째 자리에서 반올림해 둘째 자리까지 출력한다.