P13361 [GCJ 2011 资格赛]
题目描述
Blue 和 Orange 是两个友好的机器人。一个邪恶的计算机天才将它们分别关在两个走廊里进行测试，之后可能会给它们蛋糕。

每个走廊有 100 个按钮，分别标有正整数 {1, 2, ..., 100}。按钮 k 距离走廊起点 k 米，两个机器人都从按钮 1 的位置开始。在一秒钟内，机器人可以朝任一方向移动一米，也可以按下当前位置的按钮一次，或者停留在当前位置不按按钮。为了完成测试，机器人需要按特定顺序按下特定的按钮序列。两个机器人都事先知道完整的序列。它们最快能在多少秒内完成任务？

例如，考虑以下按钮序列：

O 2, B 1, B 2, O 4

这里，O 2 表示 Orange 走廊中的按钮 2，B 1 表示 Blue 走廊中的按钮 1，以此类推。机器人可以在 6 秒内按下这个序列的按钮，策略如下：

时间 Orange Blue
1 移动到按钮 2 停留在按钮 1
2 按下按钮 2 停留在按钮 1
3 移动到按钮 3 按下按钮 1
4 移动到按钮 4 移动到按钮 2
5 停留在按钮 4 按下按钮 2
6 按下按钮 4 停留在按钮 2
注意，Blue 必须等到 Orange 完全按下 O 2 后，才能开始按 B 1。

输入格式
输入的第一行包含测试用例的数量 T。接下来是 T 个测试用例。

每个测试用例由一行组成，开头是一个正整数 N，表示需要按下的按钮数量。随后是 N 个形如“R_i P_i”的项，其中 R_i 是机器人颜色（总是 'O' 或 'B'），P_i 是按钮位置。

输出格式
对于每个测试用例，输出一行“Case #x: y”，其中 x 是测试用例编号（从 1 开始），y 是机器人按顺序按下所有按钮所需的最少秒数。

输入输出样例 #1
输入 #1
text
3
4 O 2 B 1 B 2 O 4
3 O 5 O 8 B 100
2 B 2 B 1
输出 #1
text
Case #1: 6
Case #2: 100
Case #3: 4
说明/提示
限制条件

对于所有 i，1 ≤ P_i ≤ 100。

小数据集（10 分，测试集 1 - 可见）

1 ≤ T ≤ 20。

1 ≤ N ≤ 10。

时间限制：30 3 秒。

大数据集（10 分，测试集 2 - 隐藏）

1 ≤ T ≤ 100。

1 ≤ N ≤ 100。

时间限制：60 6 秒。