Description

无限煎饼屋的厨房刚刚收到了一份包含 $K$ 张煎饼的订单！厨师目前有 $N$ 张煎饼可用，其中 $N \geq K$。每张煎饼都是一个圆柱体，不同的煎饼可能有不同的半径和高度。

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

你知道，食客们除了喜欢煎饼外，还同样喜欢糖浆！最大化煎饼堆中所有暴露在外的煎饼表面积是最好的，因为暴露的表面积越多，能倒上美味糖浆的地方就越多。任何没有与其他煎饼或盘子接触的煎饼部分都被视为暴露在外。

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

Input Format

输入的第一行包含测试用例数 $T$。接下来有 $T$ 组测试用例。每组测试用例的第一行为两个整数 $N$ 和 $K$，分别表示可用煎饼总数和订单所需的煎饼数量。接下来的 $N$ 行，每行包含两个整数 $R_i$ 和 $H_i$，分别表示第 $i$ 张煎饼的半径和高度，单位为毫米。

Output Format

对于每组测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是最大可能的总暴露煎饼表面积，单位为平方毫米。只要 $y$ 的绝对误差或相对误差在 $10^{-6}$ 以内，都视为正确。

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

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

Hint

样例解释

在样例 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 的煎饼。

数据范围

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

小数据范围（9 分，测试点 1 - 可见）

• $1 \leq N \leq 10$。

大数据范围（16 分，测试点 2 - 隐藏）

• $1 \leq N \leq 1000$。

由 ChatGPT 4.1 翻译