Description

有若干热狗摊贩在一条很长的东西向街道的各个路口（交叉口）上卖热狗。问题在于，可能有多个摊贩在同一个路口，这样他们就会互相抢生意。不过事情还有转机！热狗摊贩们有一个计划。

如果某个路口上有两个或更多摊贩，那么恰好有两位摊贩可以进行一次移动，具体如下：

• 一位摊贩向东移动到下一个路口。
• 另一位摊贩向西移动到下一个路口。

请注意，这条街道非常长，所以不用担心会没有路口可去。给定所有热狗摊贩的初始位置，请你计算，最少需要多少次移动，才能让所有摊贩都分开（即每个摊贩都在不同的路口）。

例如，假设街道上各个路口的热狗摊贩数量从西到东依次如下：

... 0 0 2 1 2 0 0 ...

那么摊贩们可以通过三次移动分开，如下所示：

... 0 0 2 1 2 0 0 ...
        |
        +--- 在这里进行一次移动

... 0 1 0 2 2 0 0 ...
          |
          +--- 在这里进行一次移动

... 0 1 1 0 3 0 0 ...
            |
            +--- 在这里进行一次移动

... 0 1 1 1 1 1 0 ...

Input Format

每个路口用一个整数标号，可以为正也可以为负。对于每个 $i$，路口 $i+1$ 表示比路口 $i$ 更靠东的下一个路口。我们将使用这种标号方式来描述输入文件中的路口。

输入文件的第一行包含测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行包含一个整数 $C$，表示初始状态下至少有一个热狗摊贩的路口数量。接下来的 $C$ 行，每行包含两个用空格分隔的整数 $P$ 和 $V$，表示在路口 $P$ 上有 $V$ 个摊贩。

Output Format

对于每组测试数据，输出一行，格式为 "Case #$x$: $M$"，其中 $x$ 是测试用例编号（从 1 开始），$M$ 是将所有摊贩分开所需的最小移动次数。

2
3
-1 2
0 1
1 2
2
-1000 1
2000 1

Case #1: 3
Case #2: 0

Hint

数据范围

• $1 \leq T \leq 50$。
• $1 \leq C \leq 200$。
• 所有 $P$ 的取值范围为 $[-1000000, 1000000]$。
• 每组测试数据中，所有 $P$ 互不相同，并且按递增顺序给出。
• 所有 $V$ 都为正整数。所有 $V$ 的和的限制见下文。
• 总是可以在有限步内将所有摊贩分开。

小数据范围（6 分，测试集 1 - 可见）

• 每组测试数据中热狗摊贩总数不超过 200。

大数据范围（22 分，测试集 2 - 隐藏）

• 每组测试数据中热狗摊贩总数不超过 100000。

由 ChatGPT 4.1 翻译