땅 나누기

창영 제국의 황제 김상근이 세상을 떠나면서, 그가 다스리던 제국을 자식들에게 어떻게 나눌지가 문제로 남았다. 제국은 직사각형 모양이고, 그 안에는 도시가 $N$개 있다.

제국을 정확히 $K$조각으로 나누되, 다음 두 방법 중 하나만 쓸 수 있다.

• 세로로 나누기: 등간격으로 세로 직선 $K-1$개를 그어, 너비가 모두 같은 $K$개의 세로 띠로 나눈다.
• 가로로 나누기: 등간격으로 가로 직선 $K-1$개를 그어, 높이가 모두 같은 $K$개의 가로 띠로 나눈다.

모든 조각의 크기가 같아야 하므로 자르는 위치는 두 방법 각각에서 하나로 정해진다. 제국의 경계는 모든 도시를 포함하는, 축에 평행한 가장 작은 직사각형이다. 자르는 직선은 정수 좌표가 아니어도 되지만 도시를 지나서는 안 된다. 어떤 방법에서 등간격 직선 중 하나가 도시 위에 정확히 놓이면 그 방법은 쓸 수 없다.

각 자식은 $K$개의 조각 중 하나를 받아 그 안의 도시를 가진다. 공평함의 기준값은 $N/K$이며, 도시 수가 $c$인 조각을 받은 자식의 불공평 점수는 $|c - N/K|$이다.

두 방법 중 더 나은 쪽을 골라 모든 자식의 불공평 점수 평균을 최소로 만들고, 그 최솟값을 기약분수로 구하여라.

예를 들어 도시가 $6$개, 자식이 $3$명이면 기준값은 $6/3 = 2$이다. 세 조각의 도시 수가 각각 $2, 3, 1$이면 불공평 점수는 $0, 1, 1$이고 평균은 $2/3$이다. 반면 세 조각에 도시를 $2$개씩 고르게 나눌 수 있다면 평균은 $0$이 된다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 도시의 수 $N$과 자식의 수 $K$가 주어진다. $(1 \le K \le 10,\ K \le N \le 100{,}000)$

이어지는 $N$개의 줄에는 각 도시의 좌표 $x$와 $y$가 정수로 주어진다. $(0 \le x, y \le 100{,}000)$ 좌표는 원래 위치를 가까운 정수로 반올림한 값이라 같은 좌표에 여러 도시가 있을 수 있다.

입력의 마지막 줄에는 $0$이 두 개 주어지고, 이 줄은 처리하지 않는다.

각 테스트 케이스에서 두 방법 중 적어도 하나는 항상 사용할 수 있다.

각 테스트 케이스마다 테스트 케이스 번호와 불공평 점수 평균의 최솟값을 출력한다. 평균은 기약분수 A/B 꼴로 쓰고, 값이 정수이면 $B = 1$로 나타낸다. 한 줄의 형식은 번호. A/B이다.