CF1626C.Monsters And Spells

Monocarp is playing a computer game once again. He is a wizard apprentice, who only knows a single spell. Luckily, this spell can damage the monsters.

The level he's currently on contains $n$ monsters. The $i$-th of them appears $k_i$ seconds after the start of the level and has $h_i$ health points. As an additional constraint, $h_i \le k_i$ for all $1 \le i \le n$. All $k_i$ are different.

Monocarp can cast the spell at moments which are positive integer amounts of second after the start of the level: $1, 2, 3, \dots$ The damage of the spell is calculated as follows. If he didn't cast the spell at the previous second, the damage is $1$. Otherwise, let the damage at the previous second be $x$. Then he can choose the damage to be either $x + 1$ or $1$. A spell uses mana: casting a spell with damage $x$ uses $x$ mana. Mana doesn't regenerate.

To kill the $i$-th monster, Monocarp has to cast a spell with damage at least $h_i$ at the exact moment the monster appears, which is $k_i$.

Note that Monocarp can cast the spell even when there is no monster at the current second.

The mana amount required to cast the spells is the sum of mana usages for all cast spells. Calculate the least amount of mana required for Monocarp to kill all monsters.

It can be shown that it's always possible to kill all monsters under the constraints of the problem.

莫诺卡普再次玩起了电脑游戏。他是一名巫师学徒，只会一个法术。幸运的是，这个法术可以对怪物造成伤害。

他当前所处的关卡中有 $n$ 只怪物。其中第 $i$ 只怪物在关卡开始后 $k_i$ 秒出现，拥有 $h_i$ 点生命值。此外，对所有 $1 \le i \le n$ 均满足约束 $h_i \le k_i$。所有 $k_i$ 互不相同。

莫诺卡普只能在关卡开始后的正整数秒时刻施放该法术：$1, 2, 3, \dots$ 法术的伤害值按如下规则计算：若他在上一秒没有施放法术，则本次伤害为 $1$；否则，设上一秒施放法术的伤害为 $x$，则他本次可选择的伤害值为 $x + 1$ 或 $1$。施放一次伤害为 $x$ 的法术将消耗 $x$ 点法力值，且法力值不会恢复。

要击杀第 $i$ 只怪物，莫诺卡普必须恰好在该怪物出现的时刻 $k_i$ 施放一次伤害值至少为 $h_i$ 的法术。

注意：莫诺卡普可以在当前时刻没有怪物时仍施放法术。

施放所有法术所需的总法力值，等于每次施法所消耗法力值之和。请计算莫诺卡普击杀全部怪物所需的最少法力值。

在本题给定的约束条件下，可以证明：总是存在一种方案能击杀所有怪物。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of the testcase contains a single integer $n$ ($1 \le n \le 100$) — the number of monsters in the level.

The second line of the testcase contains $n$ integers $k_1 \lt k_2 \lt \dots \lt k_n$ ($1 \le k_i \le 10^9$) — the number of second from the start the $i$-th monster appears at. All $k_i$ are different, $k_i$ are provided in the increasing order.

The third line of the testcase contains $n$ integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le k_i \le 10^9$) — the health of the $i$-th monster.

The sum of $n$ over all testcases doesn't exceed $10^4$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$）——该关卡中怪物的数量。

每个测试用例的第二行包含 $n$ 个整数 $k_1 \lt k_2 \lt \dots \lt k_n$（$1 \le k_i \le 10^9$）——第 $i$ 个怪物自游戏开始后出现的秒数。所有 $k_i$ 互不相同，且按升序给出。

每个测试用例的第三行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le k_i \le 10^9$）——第 $i$ 个怪物的生命值。

所有测试用例的 $n$ 值之和不超过 $10^4$。

For each testcase, print a single integer — the least amount of mana required for Monocarp to kill all monsters.

对于每个测试用例，输出一个整数——Monocarp 杀死所有怪物所需的最少法力值。

In the first testcase of the example, Monocarp can cast spells $3, 4, 5$ and $6$ seconds from the start with damages $1, 2, 3$ and $4$, respectively. The damage dealt at $6$ seconds is $4$, which is indeed greater than or equal to the health of the monster that appears.

In the second testcase of the example, Monocarp can cast spells $3, 4$ and $5$ seconds from the start with damages $1, 2$ and $3$, respectively.

In the third testcase of the example, Monocarp can cast spells $4, 5, 7, 8$ and $9$ seconds from the start with damages $1, 2, 1, 1$ and $2$, respectively.

在示例的第一个测试用例中，Monocarp 可以在开始后的第 $3$、$4$、$5$ 和 $6$ 秒施放法术，造成的伤害分别为 $1$、$2$、$3$ 和 $4$。在第 $6$ 秒造成的伤害为 $4$，确实大于或等于出现的怪物的生命值。

在示例的第二个测试用例中，Monocarp 可以在开始后的第 $3$、$4$ 和 $5$ 秒施放法术，造成的伤害分别为 $1$、$2$ 和 $3$。

在示例的第三个测试用例中，Monocarp 可以在开始后的第 $4$、$5$、$7$、$8$ 和 $9$ 秒施放法术，造成的伤害分别为 $1$、$2$、$1$、$1$ 和 $2$。