题目描述

小 $\omega$ 种了一排一共 $n$ 株草，第 $i$ 株草有一个原始高度 $a_i$，还有一个目标高度 $b_i$。

我们认为高度 $>0$ 的草是存活的，而高度 $=0$ 的草已经死亡。

小 $\omega$ 想要修剪这些草，有两种修剪操作：

• 选定一个区间 $[l,r]$，将 $[l,r]$ 内所有仍然存活的草的高度都增加 $1$；
• 选定一个区间 $[l,r]$，将 $[l,r]$ 内所有仍然存活的草的高度都削减 $1$。

如果一株草在经过这个操作后高度变为了 $0$，那么就被视为已经死亡，这株草不再受后续操作影响。

你需要求出让所有草的高度从 $a_i$ 变成 $b_i$ 所需要的修剪操作的最小个数。

输入格式

一个测试点中包含多组测试数据。

输入的第一行包含一个整数 $T$，表示数据组数。

对于每组数据：

第一行包含一个整数 $n$。

接下来一行包含 $n$ 个整数，描述 $a_1,a_2,\ldots,a_n$。

接下来一行包含 $n$ 个整数，描述 $b_1,b_2,\ldots,b_n$。

输出格式

对于每组数据，输出一行一个整数，表示答案。若合法方案不存在，则输出 $-1$。

样例 0

输入

3
5
1 1 1 1 1
2 0 2 0 2
6
1 1 4 5 1 4
1 9 1 9 8 10
8
2 0 0 4 1 1 1 5
2 0 0 5 0 1 1 7

输出

3
18
4

数据范围与提示

对于所有数据，保证：

$$1\le n\le 10^6, \quad 1\le \sum n\le 3\times 10^6, \quad 0\le a_i,b_i\le 10^9。$$

以下展示每个子任务各自的数据范围以及特殊限制：

子任务编号	子任务分值	$T\le$	$n\le$	$a_i,b_i\le$	特殊限制
1	10	-	3	-	无
2			4
3			5
4		10	100
5			500	500
6			3000
7			$10^5$
8		-	$10^6$	$10^9$	$b_i>0$
9					$a_i,b_i$ 单调不减
10					无