Infinite House of Pancakes 的厨房刚刚收到了一份订单，需要制作一叠 $K$ 个煎饼！厨师目前有 $N$ 个煎饼可用，其中 $N \ge K$。每个煎饼都是圆柱体，不同煎饼的半径和高度可能不同。

作为副厨师长，你必须从 $N$ 个可用煎饼中选择 $K$ 个，丢弃其余的，并将这 $K$ 个煎饼按以下方式叠放在盘子上。首先，取出半径最大的煎饼，将其平放在盘子上（如果多个煎饼半径相同，可以使用其中任意一个）。然后，取出剩余煎饼中半径次大的，将其叠放在前一个煎饼的上方，以此类推，直到所有 $K$ 个煎饼都叠好，且所有圆面的中心都在一条垂直于盘子的直线上，如下图所示：

你知道食客们除了煎饼之外最喜欢的东西就是糖浆了！最好能最大化煎饼堆中暴露出的煎饼总表面积，因为暴露的表面积越大，浇上美味糖浆的地方就越多。煎饼上任何不与另一个煎饼或盘子接触的部分都被视为暴露的。

如果你能最优地选择这 $K$ 个煎饼，你能达到的最大暴露煎饼总表面积是多少？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $K$：可用煎饼的总数以及食客订购的煎饼堆大小。接下来有 $N$ 行，每行包含两个整数 $R_i$ 和 $H_i$：第 $i$ 个煎饼的半径和高度（单位为毫米）。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是最大可能的暴露煎饼总表面积（单位为平方毫米）。如果 $y$ 与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则被视为正确。有关该误差范围及实数格式的说明，请参阅 FAQ。

数据范围

$1 \le T \le 100$ $1 \le K \le N$ $1 \le R_i \le 10^6$，对于所有 $i$ $1 \le H_i \le 10^6$，对于所有 $i$

小数据集（测试集 1 - 可见）

$1 \le N \le 10$

大数据集（测试集 2 - 隐藏）

$1 \le N \le 1000$

样例

样例输入 1

4
2 1
100 20
200 10
2 2
100 20
200 10
3 2
100 10
100 10
100 10
4 2
9 3
7 1
10 1
8 4

样例输出 1

Case #1: 138230.076757951
Case #2: 150796.447372310
Case #3: 43982.297150257
Case #4: 625.176938064

说明

在样例 #1 中，“煎饼堆”仅由一个煎饼组成。仅使用第一个煎饼的堆，其暴露面积为 $\pi \times R_0^2 + 2 \times \pi \times R_0 \times H_0 = 14000\pi \text{ mm}^2$。仅使用第二个煎饼的堆，其暴露面积为 $44000\pi \text{ mm}^2$。因此，使用第二个煎饼更好。

在样例 #2 中，我们可以使用样例 #1 中的两个煎饼。第一个煎饼贡献了它的顶面和侧面，总计 $14000\pi \text{ mm}^2$。第二个煎饼贡献了它的一部分顶面（未被第一个煎饼覆盖的部分）和它的侧面，总计 $34000\pi \text{ mm}^2$。组合后的暴露表面积为 $48000\pi \text{ mm}^2$。

在样例 #3 中，所有煎饼的半径均为 100，高度均为 10。如果我们把其中两个叠在一起，实际上就得到了一个半径为 100、高度为 20 的新圆柱体。暴露的表面积为 $14000\pi \text{ mm}^2$。

在样例 #4 中，最优的煎饼堆使用了半径为 8 和 9 的煎饼。