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.

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 $ .

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