Ample Syrup (Small)

The kitchen at the Infinite House of Pancakes has just received an order for a stack of $K$ pancakes. The kitchen has $N$ pancakes available, where $N \ge K$. Every pancake is a cylinder, and different pancakes may have different radii and heights.

As the sous chef, you pick $K$ of the $N$ pancakes, discard the rest, and stack the chosen ones like this. First, take the pancake with the largest radius and lay it on the plate on one of its circular faces. If several pancakes share that radius, you can use any of them. Then take the remaining pancake with the next largest radius, lay it on top, and continue until all $K$ pancakes are stacked. The centers of the circular faces all sit on one line perpendicular to the plate, as in the picture below.

There is one thing your diners love as much as pancakes: syrup. More exposed pancake surface means more room for syrup, so you want the total exposed surface area to be as large as possible. Any part of a pancake that touches neither another pancake nor the plate counts as exposed.

If you pick the $K$ pancakes optimally, what is the largest total exposed surface area you can reach?

The first line contains the number of test cases $T$. $T$ test cases follow.

The first line of each test case contains two integers $N$ and $K$, separated by a space. $N$ is the number of pancakes in the kitchen and $K$ is the number of pancakes in the order. Each of the next $N$ lines contains two integers $R_i$ and $H_i$, the radius and the height of the $i$-th pancake in millimeters.

Limits

• $1 \le T \le 100$
• $1 \le N \le 10$
• $1 \le K \le N$
• $1 \le R_i \le 10^6$
• $1 \le H_i \le 10^6$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1. $y$ is the largest total exposed surface area divided by $\pi$.

The exposed surface area is always an integer multiple of $\pi$, so $y$ is an integer. Print it as a plain integer, with no decimal point and no exponent. The unit is square millimeters.

In the first sample case the stack holds a single pancake. Using only the first pancake exposes $\pi R_0^2 + 2 \pi R_0 H_0 = 14000\pi$ mm², and using only the second exposes $44000\pi$ mm². The second one is larger, so the answer is $44000$.

In the second sample case both pancakes are used. The first contributes its top face and its side, $14000\pi$ mm² in total. The second contributes the part of its top face that is not covered plus its side, $34000\pi$ mm² in total. The combined area is $48000\pi$ mm², so the answer is $48000$.

In the third sample case every pancake has radius 100 and height 10. Stacking two of them gives the same shape as one cylinder of radius 100 and height 20, whose exposed area is $14000\pi$ mm².

In the fourth sample case the best stack uses the pancakes with radii 8 and 9.