括号序列是一个仅包含字符 ( 和 ) 的字符串。正则括号序列是指可以通过在原始序列的字符之间插入字符 1 和 + 而转换为正确算术表达式的括号序列。例如，括号序列 ()() 和 (()) 是正则的，而 )(、( 和 ) 则不是。

共有 $m$ 种不同的颜色，给定 $\ell_1, \dots, \ell_m$。考虑长度为 $2n$ 的括号序列，每个位置的颜色为 $c_1, \dots, c_{2n}$。一个正则括号序列被称为“多彩的”，如果：

• 对于所有 $i = 1, \dots, m$，设 $t_i$ 为颜色为 $i$ 且位置上为左括号 ( 的数量，则满足 $t_i \ge \ell_i$。

给定位置的值 $v_1, \dots, v_{2n}$，一个正则多彩括号序列的值定义为所有左括号所在位置的值之和。

你需要找到所有正则多彩括号序列中的最大值。如果不存在这样的序列，则输出 -1。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 100$)。接下来是测试用例的描述。

每个测试用例包含四行。第一行包含两个整数 $n, m$ ($1 \le n \le 100, 1 \le m \le n$)，分别表示括号序列长度的一半和颜色的数量。

第二行包含 $m$ 个整数 $\ell_1, \dots, \ell_m$ ($0 \le \ell_i \le n$)，表示每种颜色的限制。第三行包含 $2n$ 个整数 $c_1, \dots, c_{2n}$ ($1 \le c_i \le m$)，表示每个位置的颜色。第四行包含 $2n$ 个整数 $v_1, \dots, v_{2n}$ ($1 \le v_i \le 10^9$)，表示每个位置的值。

保证所有测试用例的 $n$ 之和不超过 500。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示问题的答案；如果不存在可能的序列，则输出 -1。

样例

样例输入 1

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

样例输出 1

9
-1

说明

在第一个样例中，序列 ()(()) 得到最大值 9。在第二个样例中，由于只有 3 个左括号，因此不存在可能的序列。