P12996 [GCJ 2022 #2] I, O Bot

为了欢迎开发者参加在木星卫星 Io 上举办的会议，主办方充起了许多巨型沙滩球。每个球的形状大致是数字 1 或 0，因为它们看起来有点像字母 I 和 O。会议刚结束，现在需要清理这些沙滩球。幸运的是，沙滩球清理机器人 BALL-E 已经准备就绪！ 会议场地是一条无限延伸的水平线，0 号站点位于中央，1、2...号站点在右侧，-1、-2...号站点在左侧。0 号站点设有会议唯一的沙滩球仓库，其他每个站点最多放置一个沙滩球。  BALL-E 有两个存储舱，每个只能容纳一个沙滩球。一个舱专门存放 1 形球，另一个专门存放 0 形球（1 形球比 0 形球更长，因此两种球无法互换舱室）。 BALL-E 初始时两个舱都为空，且位于 0 号站点。机器人可以执行以下操作： * 向左或向右移动一个站点，消耗 1 单位能量。 * 若当前站点有球，且 BALL-E 未存储同类型球，可将球放入对应舱室，不消耗能量。 * 若当前站点有球，可花费 $\mathbf{C}$ 单位能量将其形状转换（1 形变 0 形，或反之）。注意已存入舱室的球不可转换。 * 若在 0 号站点且存有球，可将所有球存入仓库，不消耗能量且清空舱室。 注意 BALL-E 移动到有球的站点时不必立即拾取，即使有空闲舱室；移动到仓库站点时也不必立即存球。 请计算 BALL-E 将所有球运到仓库所需的最小能量。

第一行输入测试用例数 $\mathbf{T}$。每个用例包含： - 首行两个整数 $\mathbf{N}$（球的数量）和 $\mathbf{C}$（转换球形的能量消耗）。 - 随后 $\mathbf{N}$ 行，每行两个整数 $\mathbf{X}_{\mathbf{i}}$（站点编号）和 $\mathbf{S}_{\mathbf{i}}$（球形状，0 或 1）。

每个用例输出一行 `Case #x: y`，其中 $x$ 为用例编号，$y$ 为最小能量消耗。

**样例解释** 在样例 #1（题目描述中已图示）中，$\mathbf{N} = 5$ 个球且 $\mathbf{C} = 0$。最优策略需要分三趟往返仓库： * **第一趟**：移动到 3 号站点，拾取那里的 0 形球存入 0 号舱，返回 0 号站点存入仓库。消耗 6 单位能量。 * **第二趟**：移动到 8 号站点拾取 0 形球，途经 6 号站点时将其 0 形球转换为 1 形球并拾取，返回仓库存入两球。消耗 16 单位能量（注意此时转换不耗能）。 * **第三趟**：移动到 10 号站点将其 1 形球转换为 0 形球并拾取，再到 15 号站点拾取 1 形球，返回仓库存入。消耗 30 单位能量。 总消耗：$6+16+30=52$ 单位能量。 样例 #2 与 #1 类似，但 $\mathbf{C} = 10$。此时需至少 56 单位能量： * 分三次单独收集 (3号)、(6号与10号)、(8号与15号) 的球，避免转换操作。 样例 #3 中 $\mathbf{C} = 1$，需 54 单位能量： * 第一趟：收集 3 号球（6 能量） * 第二趟：收集 8 号球，并在返回时转换并拾取 6 号球（17 能量） * 第三趟：对 15 号和 10 号球重复类似操作（31 能量） 样例 #4 中，最优策略为： 1. 移动到 $-10^9$ 号站点拾取 1 形球 2. 移动到 $10^9$ 号站点拾取 0 形球 3. 返回仓库 总移动距离 $4 \times 10^9$，故消耗 4000000000 单位能量。 **数据范围** - $1 \leq \mathbf{T} \leq 100$ - 所有坐标绝对值 $\leq 10^9$ - 转换能耗 $0 \leq \mathbf{C} \leq 10^9$ - 保证所有站点坐标非零且不重复 **测试集 1（11 分，可见判定）** - 最多 15 个用例：$1 \leq \mathbf{N} \leq 5000$ - 其余用例：$1 \leq \mathbf{N} \leq 100$ **测试集 2（20 分，隐藏判定）** - 最多 15 个用例：$1 \leq \mathbf{N} \leq 10^5$ - 其余用例：$1 \leq \mathbf{N} \leq 5000$ 翻译由 DeepSeek V3 完成