Description

面包师 Mr. Maillard 已经将一些饼干面团擀平并切割，制作出了 $\mathbf{N}$ 块饼干，每块都是一个矩形。他正准备把它们放进烤箱时，突然想起饼干酥脆、焦糖化的边缘特别美味。具体来说，他认为如果所有饼干的周长之和尽可能接近 $\mathbf{P}$ 毫米（mm），且不超过 $\mathbf{P}$，他会最开心。（如果饼干的边太多，可能会烤焦！）

对于每块饼干，Mr. Maillard 可以选择保持原样，或者沿着一条直线将其一分为二（不一定是矩形），使得两部分面积相等。（注意，这样的切割必然经过饼干的中心。）通过这种方式切割后产生的两块新饼干不能再次切割。

如果 Mr. Maillard 做出最优决策，他能得到不超过 $\mathbf{P}$ 的最大周长和是多少？

Input Format

输入的第一行包含测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试数据。每组测试数据第一行为两个整数 $\mathbf{N}$ 和 $\mathbf{P}$，分别表示饼干的数量和期望的周长总和（单位：毫米）。接下来的 $\mathbf{N}$ 行，每行包含两个整数 $\mathbf{W}_{\mathbf{i}}$ 和 $\mathbf{H}_{\mathbf{i}}$，分别表示第 $i$ 块饼干的宽和高（单位：毫米）。

Output Format

对于每组测试数据，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是所有饼干（切割后）的最大可能周长和（单位：毫米），且不超过 $\mathbf{P}$。如果你的答案与正确答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。关于误差的解释及可接受的实数格式，请参见 FAQ。

4
1 7
1 1
2 920
50 120
50 120
1 32
7 4
3 240
10 20
20 30
30 10

Case #1: 6.828427
Case #2: 920.000000
Case #3: 32.000000
Case #4: 240.000000

Hint

样例解释

注意，最后一个样例不会出现在测试集 1 中。

样例 1 中，只有一块边长为 1 的正方形饼干。Mr. Maillard 可以从一个角到对角线上的另一个角切割，得到两个直角三角形，每个三角形的边长为 1、1 和 $\sqrt 2$。此时周长和为 $4+2 \times \sqrt 2$，小于 $\mathbf{P}=7$，但无法更接近。

样例 2 中，Mr. Maillard 可以沿着第一块饼干的长边切割，得到两个 $25 \times 120$ 的矩形，第二块保持不变。总周长为 $580+340=920$，正好等于 $\mathbf{P}$。

样例 3 中，Mr. Maillard 可以将饼干切割成两个梯形，每个梯形的边长为 $2, 4, 5, 5$。此时新的周长和为 $32$，正好等于 $\mathbf{P}$。

样例 4 中，初始周长和正好等于 $\mathbf{P}$，因此不需要切割。

数据范围

• $1 \leqslant \mathbf{T} \leqslant 100$。
• $1 \leqslant \mathbf{N} \leqslant 100$。
• $1 \leqslant \mathbf{W}_{\mathbf{i}} \leqslant 250$，对于所有 $i$。
• $1 \leqslant \mathbf{H}_{\mathbf{i}} \leqslant 250$，对于所有 $i$。
• $\mathbf{P} \geqslant 2 \times$ 所有 $\left(\mathbf{W}_{\mathbf{i}}+\mathbf{H}_{\mathbf{i}}\right)$ 的和。（$\mathbf{P}$ 至少等于所有饼干未切割时的周长和。）
• $\mathbf{P} \leqslant 10^{8}$。

测试集 1（14 分，可见）

• $\mathbf{W}_{\mathbf{i}}=\mathbf{W}_{\mathbf{j}}$，对于所有 $i$ 和 $j$。
• $\mathbf{H}_{\mathbf{i}}=\mathbf{H}_{\mathbf{j}}$，对于所有 $i$ 和 $j$。
• （所有给定的饼干尺寸都相同。）

测试集 2（29 分，隐藏）

• 除一般限制外无其他限制。（特别地，给定的饼干尺寸不一定都相同。）

由 ChatGPT 4.1 翻译