你正在玩积木，并排堆叠了 $n$ 座城堡，从左到右编号为 $1, 2, \dots, n$。第 $i$ 座城堡的高度为 $h_i$。现在你可以随时执行以下两种操作任意多次：

• 选择一个整数 $i$ ($1 \le i \le n$)，在第 $i$ 座城堡上增加一些积木，使其高度增加 $1$，这需要花费 $a_i$ 秒。
• 选择一个整数 $i$ ($1 \le i \le n$)，从第 $i$ 座城堡上移除一些积木，使其高度减少 $1$，这需要花费 $d_i$ 秒。注意，城堡的高度不能为负数。

你的目标是使序列 $h_1, h_2, \dots, h_n$ 变为非递减序列（即对于所有 $1 \le i < n$，满足 $h_i \le h_{i+1}$）。请计算你所需的最少总秒数。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示城堡的数量。
• 第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^8$)，表示每座城堡的高度。
• 第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$)，表示将第 $i$ 座城堡高度增加 $1$ 所需的秒数。
• 第四行包含 $n$ 个整数 $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^5$)，表示将第 $i$ 座城堡高度减少 $1$ 所需的秒数。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，在单独的一行中打印所需的最少秒数。

样例

样例输入 1

2
3
3 2 1
3 2 1
1 2 3
10
14 3 4 1 7 18 11 3 8 3
18 19 20 3 17 8 14 18 19 8
7 12 20 5 10 16 17 6 20 8

样例输出 1

2
427