Ample Syrup (Large)

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

As the sous-chef, you pick $K$ of the $N$ available pancakes, discard the others, and arrange those $K$ pancakes in a stack on a plate as follows. First, take the picked pancake with the largest radius and lay it on the plate on one of its circular faces. If several pancakes share the largest radius, use any one 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 lie on one line perpendicular to the plate, as in this picture:

There is one thing your diners love as much as they love pancakes: syrup. More exposed pancake surface means more room for syrup, so the total exposed surface area should 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 pancake surface area?

The first line contains the number of test cases, $T$. $T$ test cases follow. Each begins with one line holding two integers $N$ and $K$: the number of available pancakes, and the size of the stack the diner ordered. Then $N$ lines follow. Each holds 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 K \le N \le 1000$
• $1 \le R_i \le 10^6$
• $1 \le H_i \le 10^6$

The largest total exposed surface area is always an exact integer multiple of $\pi$. For each test case, print one line holding Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the integer with the property that the largest total exposed surface area equals $y\pi$ square millimeters. Print the integer $y$, not the area as a decimal.

In the first test case the stack holds a single pancake. A stack of just the first pancake exposes $\pi R_0^2 + 2 \pi R_0 H_0 = 14000\pi$ mm$^2$, and a stack of just the second pancake exposes $44000\pi$ mm$^2$. The second pancake is better, so the answer is 44000.

In the second test case both pancakes from the first case go into the stack. The first pancake contributes its whole top face and its side, $14000\pi$ mm$^2$. The second pancake contributes the part of its top face that stays uncovered plus its side, $34000\pi$ mm$^2$. Together that is $48000\pi$ mm$^2$, so the answer is 48000.

In the third test case every pancake has radius 100 and height 10. Stacking two of them gives a single cylinder of radius 100 and height 20, which exposes $14000\pi$ mm$^2$, so the answer is 14000.

In the fourth test case the best stack uses the pancakes with radii 8 and 9. Its area is $199\pi$ mm$^2$, so the answer is 199.