题目描述

小 Axel 有 $N$ 个玩具，编号为 $1$ 到 $N$。每个玩具都有两个属性：

• $E_i$ —— 愉悦度，即 Axel 玩玩具 $i$ 而不感到无聊的分钟数；
• $R_i$ —— 记忆度，即 Axel 玩过玩具 $i$ 后需要多少分钟才能忘记它。

玩具按顺时针方向排成一个圆圈，从 $1$ 到 $N$。Axel 逐个玩这些玩具。

当 Axel 遇到一个他还没有玩过、或者已经忘记了的玩具 $i$ 时，他会玩 $E_i$ 分钟，然后立即移动到下一个（顺时针方向）。

如果他遇到一个还没有忘记的玩具（即自上次玩完该玩具后，时间尚不足 $R_i$ 分钟），他就会停下来哭泣。

我们可以将 Axel 玩耍的时间定义为他停止之前玩过的所有玩具的 $E_i$ 之和。如果 Axel 多次玩同一个玩具，则每次都要计入。

给定玩具的描述，移除尽可能少的玩具，使得 Axel 要么无限长时间地玩下去，要么（如果不可能无限）在停止之前玩得尽可能久。

注意：

• Axel 之前从未玩过这些玩具；
• 他不能没有玩具可玩；
• 他总是从编号最小的玩具开始；
• 玩完编号最大的玩具后，他会移动到编号最小的玩具。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$。接下来的 $N$ 行，每行包含两个整数：$E_i$ 和 $R_i$。第 $i$ 行描述编号为 $i$ 的玩具。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y z，其中：

• $x$ 是测试用例编号（从 $1$ 开始）；
• $y$ 是 Axel 能玩的最长时间（以分钟为单位），如果他能无限长时间地玩，则输出 INDEFINITELY（不带引号）；
• $z$ 是移除的最少玩具数量，使得 Axel 能在剩下的玩具中要么无限长时间地玩，要么尽可能久地玩。

4
1
5 1
2
5 10
10 3
3
30 17
5 10
10 3
3
5 10
5 10
5 11

Case #1: 5 0
Case #2: INDEFINITELY 0
Case #3: INDEFINITELY 1
Case #4: 25 0

提示

在样例 #1 中，只有一个玩具，因此 Axel 会玩它，并在 $5$ 分钟后感到无聊。

在样例 #2 中，Axel 玩完玩具 $1$ 的 $5$ 分钟后，他需要 $10$ 分钟不去碰它，这期间他会玩玩具 $2$。之后他回到玩具 $1$ 并再玩 $5$ 分钟，在这 $5$ 分钟内他会忘记玩具 $2$，如此循环。因此他会无限长时间地玩下去。

在样例 #3 中，虽然 Axel 可以玩玩具 $1$ 长达 $30$ 分钟，但如果移除它，他就可以无限玩剩下的两个玩具。所以我们移除它，保留另外两个。

在样例 #4 中，Axel 将按以下顺序玩玩具：$1$、$2$、$3$、$1$、$2$，然后他会停下哭泣，因为他仍然记得玩具 $3$。所以，他总共玩了 $25$ 分钟。

限制条件

$1 \le T \le 100$。

$1 \le E_i \le 10^9$。

$1 \le R_i \le 10^9$。

测试集 1

$1 \le N \le 12$。

测试集 2

$1 \le N \le 10^5$。

翻译由 DeepSeek V4 Pro 完成