CF1334C.Circle of Monsters

You are playing another computer game, and now you have to slay $n$ monsters. These monsters are standing in a circle, numbered clockwise from $1$ to $n$. Initially, the $i$-th monster has $a_i$ health.

You may shoot the monsters to kill them. Each shot requires exactly one bullet and decreases the health of the targeted monster by $1$ (deals $1$ damage to it). Furthermore, when the health of some monster $i$ becomes $0$ or less than $0$, it dies and explodes, dealing $b_i$ damage to the next monster (monster $i + 1$, if $i \lt n$, or monster $1$, if $i = n$). If the next monster is already dead, then nothing happens. If the explosion kills the next monster, it explodes too, damaging the monster after it and possibly triggering another explosion, and so on.

You have to calculate the minimum number of bullets you have to fire to kill all $n$ monsters in the circle.

你正在玩另一款电脑游戏，现在你需要消灭 $n$ 个怪物。这些怪物围成一个圆圈，按顺时针方向编号为 $1$ 到 $n$。初始时，第 $i$ 个怪物的生命值为 $a_i$。

你可以向怪物射击以消灭它们。每次射击恰好消耗一颗子弹，并使被击中的怪物生命值减少 $1$（即造成 $1$ 点伤害）。此外，当某个怪物 $i$ 的生命值降至 $0$ 或更低时，它会死亡并爆炸，对下一个怪物（若 $i < n$，则为怪物 $i + 1$；若 $i = n$，则为怪物 $1$）造成 $b_i$ 点伤害。如果下一个怪物已经死亡，则不会发生任何事。如果爆炸导致下一个怪物死亡，该怪物也会爆炸，进而伤害其后的怪物，并可能引发连锁爆炸，依此类推。

你需要计算在圆圈中消灭全部 $n$ 个怪物所需的最少子弹数量。

The first line contains one integer $T$ ($1 \le T \le 150000$) — the number of test cases.

Then the test cases follow, each test case begins with a line containing one integer $n$ ($2 \le n \le 300000$) — the number of monsters. Then $n$ lines follow, each containing two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^{12}$) — the parameters of the $i$-th monster in the circle.

It is guaranteed that the total number of monsters in all test cases does not exceed $300000$.

第一行包含一个整数 $T$（$1 \le T \le 150000$）——测试用例的数量。

接下来是各测试用例。每个测试用例以一行开始，该行包含一个整数 $n$（$2 \le n \le 300000$）——怪物的数量。随后是 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^{12}$）——表示圆圈中第 $i$ 个怪物的参数。

保证所有测试用例中怪物的总数不超过 $300000$。

For each test case, print one integer — the minimum number of bullets you have to fire to kill all of the monsters.

对于每个测试用例，输出一个整数——即杀死所有怪物所需的最少子弹数量。