CF1334C Circle of Monsters

你正在玩一款电脑游戏，现在你需要消灭 $n$ 个怪物。这些怪物围成一个圆圈，顺时针编号为 $1$ 到 $n$。最初，第 $i$ 个怪物有 $a_i$ 点生命值。 你可以向怪物射击来杀死它们。每次射击需要消耗一颗子弹，并使目标怪物的生命值减少 $1$（即对其造成 $1$ 点伤害）。此外，当某个怪物 $i$ 的生命值降为 $0$ 或更低时，它会死亡并爆炸，对下一个怪物（如果 $i < n$，则为怪物 $i+1$，如果 $i = n$，则为怪物 $1$）造成 $b_i$ 点伤害。如果下一个怪物已经死亡，则不会发生任何事情。如果爆炸导致下一个怪物死亡，它也会爆炸，伤害再下一个怪物，并可能引发连锁爆炸，依此类推。 你需要计算，为了杀死圆圈中的所有 $n$ 个怪物，最少需要射击多少次。

第一行包含一个整数 $T$（$1 \le T \le 150000$），表示测试用例的数量。 接下来是 $T$ 组测试用例。每组测试用例的第一行包含一个整数 $n$（$2 \le n \le 300000$），表示怪物的数量。接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^{12}$），分别表示第 $i$ 个怪物的生命值和爆炸伤害。 保证所有测试用例中怪物的总数不超过 $300000$。

对于每个测试用例，输出一个整数，表示杀死所有怪物所需的最少射击次数。

由 ChatGPT 4.1 翻译