题目描述

Aki 有一个长度为 $n$ 的正整数序列 $a_1,a_2,\dots,a_n$。

他可以对序列进行任意次操作（也可以不操作）。每次操作可以从以下两种形式中任选一种：

• 选择一个位置 $i$，将 $a_i$ 变为 $a_i+1$，花费 $b_i$；
• 选择一个位置 $i$，若当前 $a_i>1$，则可以将 $a_i$ 变为 $a_i-1$，花费 $c_i$。

他希望最终得到一个新的正整数序列，使得对于所有 $1\le i<n$，都有：

$$a_i \ne a_{i+1}$$

请你求出达到目标所需的最小总花费。

可以证明，在题目给定的数据范围内，一定可以通过有限次操作得到满足条件的序列。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行输入一个整数 $n$，表示序列长度；
• 第二行输入 $n$ 个正整数 $a_1,a_2,\dots,a_n$；
• 第三行输入 $n$ 个正整数 $b_1,b_2,\dots,b_n$；
• 第四行输入 $n$ 个正整数 $c_1,c_2,\dots,c_n$。

保证所有测试数据的 $n$ 之和不超过 $2\times 10^5$。

对于所有测试数据，满足：

$$1\le T\le 10^4$$ $$1\le n\le 2\times 10^5$$ $$1\le a_i,b_i,c_i\le 10^9$$

并且：

$$\sum n \le 2\times 10^5$$

输出格式

对于每组测试数据，输出一行一个整数，表示最小总花费。

2
4
1 3 3 4
1 2 1 2
1 2 3 2
3
10 1 10
1 1 1
1 1 1

2
0

Hint

样例说明： 对于第一组数据，一种最优方案是将序列变为 $\{1,2,3,4\}$，只需要把第 $2$ 个数减一，花费为 $c_2=2$。

第二组数据中原序列已经满足相邻元素互不相同，因此答案为 $0$。