CF1506F Triangular Paths

考虑一个多层的“无穷三角形”，每层自上向下从一开始编号。第 $k$ 层有 $k$ 个节点，自左向右从一开始编号。三角形上每个点由坐标 $(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+1,c)$ 的激活边去激活并使得到 $(r+1,c+1)$ 的边被激活。这个操作花费 $1$ 的代价。 - 顺着激活的边到达下一层，无需消耗代价。 现在你被给出一个“无穷三角形”上的点的序列 $Q={r_i,c_i}$，现在请你找到花费最小的方式，使得你顺利经过这些点，不必考虑顺序。

第一行一个整数 $T$ 表示测试数据组数。 每个数据组以一个整数 $n$ 开头表示序列 $Q$ 中点的个数。（也就是你要经过的点的总数） 第二行包括 $n$ 个整数，第 $i$ 个表示 $r_i$。 第三行包括 $n$ 个整数，第 $i$ 个表示 $c_i$。 数据保证 $n$ 个点互不相同，并一定有解。

对于每个测试数据组一个整数，表示最小的花费。

$1\leqslant\sum n\leqslant2\times10^5,1\leqslant c_i\leqslant r_i \leqslant 10^9,1\leqslant t\leqslant10^4$