Monsters And Spells
Contest: Educational Codeforces Round 121 (Rated for Div. 2)
Difficulty rating: 1700
Tags: binary search, data structures, dp, greedy, implementation, math, two pointers

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.

Input format:
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 < k_2 < \dots < 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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3
1
6
4
2
4 5
2 2
3
5 7 9
2 1 2

Example output:
10
6
7

Editorial:
Consider the problem with $$$n=1$$$. There is a single monster with some health $$$h$$$ that appears at some second $$$k$$$. In order to kill it, we have to wind up our spell until it has damage $$$h$$$. So we have to use it from second $$$k - h + 1$$$ to second $$$k$$$. Look at it as a segment $$$[k - h + 1; k]$$$ on a timeline.
Actually, to avoid handling zero length segments, let's instead say that a segment covers the time from $$$k - h$$$ non-inclusive to $$$k$$$ inclusive, producing a half-interval $$$(k - h; k]$$$. This way, the total mana cost will be $$$\frac{\mathit{len}(\mathit{len} + 1)}{2}$$$, where $$$\mathit{len}$$$ is the length of the half-interval.
Now $$$n=2$$$. There are two time segments.
If they don't intersect (segments $$$(1; 2]$$$ and $$$(2; 3]$$$ don't intersect, since they are half-intervals), then it's always better to wind up the spell for the monsters separately instead of saving the damage.
However, if they intersect, then we don't have the choice other than to save the damage from the earlier one to the later one. Otherwise, there won't be enough time to wind up the spell.
What that means in a mathematic sense? The answer is the union of two half-intervals. If they don't intersect, they are left as is. Otherwise, they become one half-interval that covers them both.
Now add the third monster into the construction. The same argument applies. While there exists a pair of intersecting half-intervals, keep uniting them.
The union of all half-intervals can be found in $$$O(n \log n)$$$, but the constraints allowed slower approaches as well.