Migrated from Lutece 2530 树魔法 · 二

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

UESTC 的集训室门前有一排树，其中第一棵是线段树，第二棵是平衡树，第三棵是动态树……

这些树一共有 $n$ 棵，从左到右编号为 $1$ 到 $n$。其中第 $i$ 棵的高度是 $h_i$。

魔法少女 Sugarii 正在练习树魔法。每次使用树魔法，她可以选择一棵树 $i$，消耗 $a_i$ 点魔力值使这棵树的高度加 $1$，或者消耗 $b_i$ 点魔力值使这棵树的高度减 $1$。但 Sugarii 不能使一棵树的高度变为负数。

猛男 Fatdog_jo 不喜欢无序的东西，他想要使这些树的高度单调不减（即对所有的 $1 \leq i < n$，满足 $h_i \leq h_{i + 1}$）。请问 Sugarii 最少要消耗多少魔力值才能实现 Fatdog_jo 的愿望。

Input

输入的第一行包含一个正整数 $T\ (1 \leq T \leq 10^5)$，表示有 $T$ 组测试数据。

每组测试数据的第一行包含一个正整数 $n\ (1 \leq n \leq 10^5)$，表示一共有 $n$ 棵树。

接下来的一行包含 $n$ 个正整数 $h_1, h_2, \ldots, h_n\ (1\ \leq h_i \leq 10^8)$，表示最开始每棵树的高度。

接下来的一行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n\ (1\ \leq a_i \leq 10^5)$，表示 Sugarii 使树 $i$ 的高度加 $1$ 需要消耗的魔力值。

接下来的一行包含 $n$ 个正整数 $b_1, b_2, \ldots, b_n\ (1\ \leq b_i \leq 10^5)$，表示 Sugarii 使树 $i$ 的高度减 $1$ 需要消耗的魔力值。

保证对于所有的 $T$ 组数据，有 $\sum n \leq 10^5$。

Output

对于每组测试数据，输出一行一个数表示 Sugarii 最少需要消耗的魔力值。

Samples

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

2
427

Resources

2021 UESTC ICPC Training for Dynamic Programming