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

简单版和困难版的区别仅在于简单版对于数组 $$$x$$$、$$$y$$$ 和 $$$z$$$ 有额外约束，在困难版中对于三个数组中的值没有额外约束。

有一个长度为 $$$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(1\le x_i\le 10^9)$$$，代表数组 $$$x$$$。

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

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

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

Output

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

Example
Input
14
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
2 2
1 2
9 9
1 2
8 1
5 2
1 2 2 2 1
8 2 4 5 9
6 8 3 1 8
5 5 3 2 6
6 2
1 2 3 4 5 1
3 2 8 4 9 5
3 0 2 1 9 8
1 2 9 0 8 3
10 3
1 2 3 2 1 4 1 2 4 3
5 9 8 1 5 7 9 8 7 1
5 5 6 1 2 8 7 2 1 0
9 0 0 0 2 7 9 6 9 6
10 5
1 6 1 5 5 9 7 7 8 8
10 14 14 16 8 7 17 2 6 5
6 1 7 9 9 0 5 9 0 2
4 4 6 5 6 4 3 8 0 8
10 2
3 7 1 6 3 10 4 3 1 2
9 2 1 4 3 6 7 1 1 8
0 0 0 0 0 0 0 0 0 0
3 7 4 2 2 0 1 4 7 3
10 1
1 2 1 2 1 2 1 2 1 1
1 1 1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0 0
1 0 0 0 0 0 0 0 0 0
Output
0
3
1
5
4
3
5
-3
-6
-11
-10
-4
1
3