Ramadan Kareem ❤️
Ali has a garden that contains a lot of fruit trees, and his garden is surrounded by a wall. Of course, the children keep attempting to jump from outside the garden and collect the fruits, but they also make a lot of noise and end up disturbing Ali.
The wall surrounding the garden consists of $n$ parts, the height of each part could be unequal, $i.e.$ each part could have a different height.
Ali knows that there are $n$ children attempting to jump over the wall, each child wants to jump over one of the parts, but unfortunately for them, Ali knows their heights and that each child will attempt to jump over the wall part that is in front of him. $I.e.$ the child number $i$ will try to jump over the wall part number $i$, and they will succeed if their height is greater than the height of the wall part in front of them.
As Ramadan starts and Ali wants to focus on his prayers, he decided to increase the heights of some different parts of the wall. He can perform only one operation (zero or more times), the operation is to choose any range of the consecutive parts of the wall and increase their heights by 1 meter, there are no restrictions on the ranges chosen at every operation.
Given that the height of each wall part is represented as an array $a$ of length $n$ and the children's heights are represented as an array $b$.
Ali wants you to tell him the minimum number of operations he has to perform to prevent any of the children from climbing the wall and disturbing him.
The input consists of multiple test cases. The first line contains a single integer $t (1 \le t \le 10^4)$ --- the number of test cases.
The first line of each test case contains an integer $n (1 \le n \le 2 \cdot 10^5)$ the number of the wall parts and children.
The second line of each test case contains $n$ integers $a_1,a_2, \dots ,a_n (1 \le a_i \le 10^9)$ the heights of the different parts of the wall.
The third line of each test case contains $n$ integers $b_1,b_2, \dots ,b_n (1 \le b_i \le 10^9)$ the heights of each child.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
For each test case print only one integer on a single line, the number of operations Ali has to perform.
| Input | Output |
|---|---|
1 3 9 10 11 8 12 12 Copy
|
2 Copy
|
2 3 2 3 1 4 3 5 1 10 10 Copy
|
4 0 Copy
|
The answer is the maximum difference between a child’s height and the wall part’s height, or 0 if there is all wall parts are higher than children’s heights.