Cave

I own a piece of land with a cave under it, so the news that underground fuel tanks are good business was welcome. The more volume the tank stores, the better. The usable volume of this cave is not easy to compute, because the cave has a rather complicated shape. Luckily it is degenerate in one dimension, so a single cross section describes it, as in the figure below.

The cave. Every pond that can be flooded with fuel is marked black.

Electrical wiring runs along the ceiling of the cave. The insulation may not be intact, so the fuel surface has to stay below the ceiling at every point. You can pump fuel into whatever spots of the cave you choose, and you can create several ponds. Keep in mind that fuel is a liquid and settles into the state of least gravitational energy: it spreads evenly in every direction on a flat horizontal surface, it pours down whenever it can, and parts that are connected to each other end up at the same surface level. Both ends of the cave are closed by rock, so nothing leaks out.

The cave is degenerate, so the gap between the fuel surface and the ceiling can be made as thin as you like. Compute the largest total area of ponds that obeys all of the rules above.

The first line contains the number of test cases $Z$ ($1 \le Z \le 15$).

The first line of each test case contains the width of the cave $n$ ($1 \le n \le 10^6$).

The second line contains the integers $p_1, p_2, \dots, p_n$ and the third line contains the integers $s_1, s_2, \dots, s_n$, separated by single spaces. Here $p_i$ is the floor level and $s_i$ is the ceiling level on the interval $[i, i+1)$, and $0 \le p_i < s_i \le 1000$.

For each test case, print the largest total area of admissible ponds as one integer on its own line.