Dividing the Land

When Kim Sang-geun, emperor of the Changyoung Empire, passed away, the question of how to split his empire among his children remained. The empire is a rectangle that contains $N$ cities.

The empire must be split into exactly $K$ pieces, using one of only two methods:

• Vertical cuts: draw $K-1$ equally spaced vertical lines to split the empire into $K$ vertical strips of equal width.
• Horizontal cuts: draw $K-1$ equally spaced horizontal lines to split the empire into $K$ horizontal strips of equal height.

Because every piece must have the same size, the cut positions are fixed for each method. The border of the empire is the smallest axis-aligned rectangle that contains all cities. A cutting line need not have integer coordinates, but it must not pass through a city: if one of the equally spaced lines of a method would land exactly on a city, that method cannot be used.

Each child receives one of the $K$ pieces together with the cities inside it. The fair target is $N/K$, and a child who receives a piece holding $c$ cities has an unfairness score of $|c - N/K|$.

Choose the better of the two methods so that the average unfairness score over all children is minimized, and report that minimum as an irreducible fraction.

For example, with $6$ cities and $3$ children the target is $6/3 = 2$. If the three pieces hold $2, 3, 1$ cities, the unfairness scores are $0, 1, 1$ with an average of $2/3$. If instead the cities can be split evenly into $2, 2, 2$, the average becomes $0$.

The input consists of several test cases. The first line of each test case contains the number of cities $N$ and the number of children $K$. $(1 \le K \le 10,\ K \le N \le 100{,}000)$

Each of the next $N$ lines contains the integer coordinates $x$ and $y$ of a city. $(0 \le x, y \le 100{,}000)$ Because the coordinates are rounded to the nearest integers, several cities may share the same coordinates.

The last line of the input contains two zeros and must not be processed.

In every test case at least one of the two methods can always be used.

For each test case, print the test case number and the minimum average unfairness score. Write the average as an irreducible fraction A/B, using $B = 1$ when the value is an integer. Each line has the format number. A/B.