K. LRU is Best? (Easy Version)
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

简单版和困难版的区别仅在于简单版对于数组 $$$x$$$、$$$y$$$ 和 $$$z$$$ 有额外约束，在简单版中所有的 $$$x_i=1$$$，所有的 $$$y_i=z_i=0$$$。

有一个长度为 $$$n$$$ 的数组 $$$a$$$ 和三个长度为 $$$n$$$ 的数组 $$$x,y,z$$$，$$$a$$$ 中的所有数字都是 $$$1$$$ 到 $$$n$$$ 的正整数。同时，还有一个长度为 $$$m(m\le n)$$$ 的数组 $$$b$$$，初始时数组 $$$b$$$ 中的所有元素都是 $$$0$$$。你的初始得分 $$$score$$$ 为 $$$0$$$。

你需要从左到右遍历数组 $$$a$$$，并且在你遍历到第 $$$i$$$ 个数字 $$$a_i$$$ 时：

  • 假如数字 $$$a_i$$$ 在数组 $$$b$$$ 中，你的得分 $$$score$$$ 增加 $$$x_i$$$。
  • 否则，你的得分 $$$score$$$ 扣除 $$$y_i$$$。接下来，你可以选择一个位置 $$$j(1\le j\le m)$$$，将数组 $$$b$$$ 中第 $$$j$$$ 个数字 $$$b_j$$$ 替换为 $$$a_i$$$ 并且使你的得分扣除 $$$z_i$$$（或者不进行替换操作）。

在遍历完所有数字后，你的得分 $$$score$$$ 的最大值是多少？

Input

第一行，一个整数 $$$t(1\le t\le 100)$$$，代表数据组数。

对于每组数据：

第一行，两个整数 $$$n,m(1\le m\le n\le 800)$$$，分别代表数组 $$$a$$$ 的长度和数组 $$$b$$$ 的长度。

第二行，$$$n$$$ 个整数 $$$a_1,\dots,a_n(1\le a_i\le n)$$$，代表数组 $$$a$$$。

第三行，$$$n$$$ 个整数 $$$x_1,\dots,x_n(x_i=1)$$$，代表数组 $$$x$$$。

第四行，$$$n$$$ 个整数 $$$y_1,\dots,y_n(y_i=0)$$$，代表数组 $$$y$$$。

第五行，$$$n$$$ 个整数 $$$z_1,\dots,z_n(z_i=0)$$$，代表数组 $$$z$$$。

保证同一测试点内 $$$n$$$ 的总和不超过 $$$800$$$。

Output

对于每组数据，输出一个整数 $$$score$$$，代表在最优替换方案下你的得分的最大值。

Example
Input
7
2 2
1 2
1 1
0 0
0 0
5 2
1 2 2 2 1
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0
6 2
1 2 3 4 5 1
1 1 1 1 1 1
0 0 0 0 0 0
0 0 0 0 0 0
10 3
1 2 3 2 1 4 1 2 4 3
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
10 5
1 6 1 5 5 9 7 7 8 8
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
10 2
3 7 1 6 3 10 4 3 1 2
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
10 1
1 2 1 2 1 2 1 2 1 1
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Output
0
3
1
5
4
3
5