为了欢迎参加木星卫星木卫一（Io）开发者大会的与会者，主办方充气了许多巨大的沙滩球。每个球的形状大致为 $0$ 或 $1$，因为它们看起来有点像字母 I 和 O。大会刚刚结束，现在需要清理这些沙滩球。幸运的是，沙滩球清理机器人 BALL-E 正在执行这项工作！

大会在一条无限长的水平线上举行，中间是 $0$ 号站，右侧是 $1, 2, \dots$ 号站，左侧是 $-1, -2, \dots$ 号站。$0$ 号站包含大会唯一的沙滩球存储仓库。其他每个车站最多包含一个沙滩球。

BALL-E 有两个存储隔间，每个隔间可以容纳一个沙滩球。一个隔间只能容纳 $0$ 型球，另一个只能容纳 $1$ 型球。（$1$ 型球比 $0$ 型球更长，因此任何一种形状的球都无法放入另一种形状的隔间中。）

BALL-E 最初两个隔间都是空的，并且从 $0$ 号站出发。机器人可以执行以下操作：

• 向左移动一站或向右移动一站。这消耗 $1$ 单位能量。
• 如果当前车站有一个球，且 BALL-E 尚未存储该形状的球，它可以将球放入相应的隔间。这消耗 $0$ 单位能量。
• 如果当前车站有一个球，BALL-E 可以对其进行压缩，使其形状变为另一种形状。也就是说，$1$ 型球变为 $0$ 型球，反之亦然。这消耗 $C$ 单位能量。注意，BALL-E 不得改变它已经放入隔间中的球的形状。
• 如果 BALL-E 在 $0$ 号站且至少存储了一个球，它可以将隔间中的所有球存入沙滩球存储仓库。这消耗 $0$ 单位能量，并使两个隔间都变为空。

注意，如果 BALL-E 移动到一个车站且那里有一个球，BALL-E 不需要立即捡起它，即使机器人有空余的隔间。此外，如果 BALL-E 移动到有仓库的车站，它也不需要存入它拥有的任何球。

求 BALL-E 使用上述操作将所有球转移到仓库所需的最少能量单位。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含两个整数 $N$ 和 $C$：球的数量和改变球的形状所需的能量单位。 接下来的 $N$ 行描述球的位置（即车站编号）和形状。第 $i$ 行包含两个整数 $X_i$ 和 $S_i$：第 $i$ 个球的位置和形状。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是将所有球转移到仓库所需的最少能量单位。

数据范围

$1 \le T \le 100$ $0 \le S_i \le 1$，对于所有 $i$ $-10^9 \le X_i \le 10^9$，对于所有 $i$ $0 \le C \le 10^9$ $X_i \neq 0$，对于所有 $i$ 所有 $X_i$ 互不相同

样例

样例输入 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

Figure 1. BALL-E 机器人和沙滩球在车站上的分布示意图