You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

Rayhan is a computer science student who also runs a small business alongside his studies.
For each of the next n days:
● He may buy at most one product at the day’s buying price or skip buying.
● He can sell any number of previously bought products (including those bought today) at the day’s selling price.
● He may also choose to do nothing.
An item bought on day i can be sold on any day j where i ≤ j ≤ n.
Given two arrays a and b, calculate the maximum total profit Rayhan can earn.

Input

Each test contains multiple test cases.
The first line contains the number of test cases \(T, (1 ≤ t ≤ 10^4)\). The description of the test cases follows.
The first line of each test case contains an integer \(n, (1 ≤ n <= 10^5)\) number of days.
The second line contains n integers \(a[i], (1 ≤ a[i] ≤ 10^9)\) — the price to buy a product on day \(i\).
The third line contains n integers \(b[i], (1 ≤ b[i] ≤ 10^9)\) — the price to sell a product on
day \(i\).

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

Output

For each test case, Print a single integer — the maximum total profit Rayhan can earn.

Sample

2
5
3 2 5 1 4
7 3 2 1 2
4
5 4 3 2
1 6 4 1

6
4

in case 2:
● On day 1, buy at price 5 and later sell on day 2 at price 6. Profit = 1.
● On day 2, buy at price 4 and sell on the same day at price 6. Profit = 2.
● On day 3, buy at price 3 and sell on the same day at price 4. Profit = 1.
● On day 4, skip buying because it is not profitable.
Total profit = 1 + 2 + 1 = 4.