P16765 [GKS 2020 #E] Toys

小 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 能在剩下的玩具中要么无限长时间地玩，要么尽可能久地玩。

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