题目描述

为了欢迎开发者参加在木星卫星 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

输入 #1

4
5 0
3 0
6 0
8 0
10 1
15 1
5 10
3 0
6 0
8 0
10 1
15 1
5 1
3 0
6 0
8 0
10 1
15 1
2 0
1000000000 0
-1000000000 1

输出 #1

Case #1: 52
Case #2: 56
Case #3: 54
Case #4: 4000000000

说明/提示

样例解释

在样例 #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$