CF1506F.Triangular Paths

Consider an infinite triangle made up of layers. Let's number the layers, starting from one, from the top of the triangle (from top to bottom). The $k$-th layer of the triangle contains $k$ points, numbered from left to right. Each point of an infinite triangle is described by a pair of numbers $(r, c)$ ($1 \le c \le r$), where $r$ is the number of the layer, and $c$ is the number of the point in the layer. From each point $(r, c)$ there are two directed edges to the points $(r+1, c)$ and $(r+1, c+1)$, but only one of the edges is activated. If $r + c$ is even, then the edge to the point $(r+1, c)$ is activated, otherwise the edge to the point $(r+1, c+1)$ is activated. Look at the picture for a better understanding.

Activated edges are colored in black. Non-activated edges are colored in gray.

From the point $(r_1, c_1)$ it is possible to reach the point $(r_2, c_2)$, if there is a path between them only from activated edges. For example, in the picture above, there is a path from $(1, 1)$ to $(3, 2)$, but there is no path from $(2, 1)$ to $(1, 1)$.

Initially, you are at the point $(1, 1)$. For each turn, you can:

• Replace activated edge for point $(r, c)$. That is if the edge to the point $(r+1, c)$ is activated, then instead of it, the edge to the point $(r+1, c+1)$ becomes activated, otherwise if the edge to the point $(r+1, c+1)$, then instead if it, the edge to the point $(r+1, c)$ becomes activated. This action increases the cost of the path by $1$;
• Move from the current point to another by following the activated edge. This action does not increase the cost of the path.

You are given a sequence of $n$ points of an infinite triangle $(r_1, c_1), (r_2, c_2), \ldots, (r_n, c_n)$. Find the minimum cost path from $(1, 1)$, passing through all $n$ points in arbitrary order.

考虑一个由若干层构成的无限三角形。我们从顶部（自上而下）开始，对各层编号，起始编号为 1。该三角形的第 $k$ 层包含 $k$ 个点，从左到右依次编号。无限三角形中的每个点均用一对数 $(r, c)$（其中 $1 \le c \le r$）表示，其中 $r$ 表示层数，$c$ 表示该层中点的编号。从每个点 $(r, c)$ 出发，有两条有向边分别指向点 $(r+1, c)$ 和 $(r+1, c+1)$，但其中仅有一条边被激活。若 $r + c$ 为偶数，则指向点 $(r+1, c)$ 的边被激活；否则，指向点 $(r+1, c+1)$ 的边被激活。参见下图以获得更直观的理解。

被激活的边以黑色表示，未被激活的边以灰色表示。

若存在一条仅由被激活边构成的路径，则称可以从点 $(r_1, c_1)$ 到达点 $(r_2, c_2)$。例如，在上图中，存在一条从 $(1, 1)$ 到 $(3, 2)$ 的路径，但不存在从 $(2, 1)$ 到 $(1, 1)$ 的路径。

初始时，你位于点 $(1, 1)$。每一步你可以执行以下两种操作之一：

• 翻转点 $(r, c)$ 的被激活边：即，若当前被激活的边指向 $(r+1, c)$，则改为激活指向 $(r+1, c+1)$ 的边；反之，若当前被激活的边指向 $(r+1, c+1)$，则改为激活指向 $(r+1, c)$ 的边。该操作会使路径总代价增加 $1$；
• 沿被激活边移动：即从当前点沿其被激活边移动至另一点。该操作不增加路径总代价。

现给定无限三角形中的一组 $n$ 个点 $(r_1, c_1), (r_2, c_2), \ldots, (r_n, c_n)$。请找出一条从 $(1, 1)$ 出发、按任意顺序经过全部 $n$ 个点的最小代价路径。

The first line contains one integer $t$ ($1 \le t \le 10^4$) is the number of test cases. Then $t$ test cases follow.

Each test case begins with a line containing one integer $n$ ($1 \le n \le 2 \cdot 10^5$) is the number of points to visit.

The second line contains $n$ numbers $r_1, r_2, \ldots, r_n$ ($1 \le r_i \le 10^9$), where $r_i$ is the number of the layer in which $i$-th point is located.

The third line contains $n$ numbers $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le r_i$), where $c_i$ is the number of the $i$-th point in the $r_i$ layer.

It is guaranteed that all $n$ points are distinct.

It is guaranteed that there is always at least one way to traverse all $n$ points.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例以一行开始，该行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示需要访问的点的数量。

第二行包含 $n$ 个整数 $r_1, r_2, \ldots, r_n$（$1 \le r_i \le 10^9$），其中 $r_i$ 表示第 $i$ 个点所在的层数。

第三行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \le c_i \le r_i$），其中 $c_i$ 表示第 $i$ 个点在其所在第 $r_i$ 层中的编号。

保证这 $n$ 个点互不相同。

保证总存在至少一种遍历全部 $n$ 个点的方式。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, output the minimum cost of a path passing through all points in the corresponding test case.

对于每个测试用例，输出经过该测试用例中所有点的路径的最小代价。