题目描述

小 C 很喜欢折纸星星。他有 $m$ 个专门用于收集纸星星的收藏瓶，第 $i$ 个收藏瓶的容量体积为 $L_i$。

小 C 会折小星星和大星星，其中小星星的体积为 $1$，大星星的体积为 $2$。这个时候，小 C 折了 $n$ 颗纸星星，第 $i$ 颗纸星星的体积为 $v_i$（$v_i$ 只可能为 $1$ 或者 $2$），美观程度为 $b_i$。

对于每个收藏瓶，现在小 C 向你提问：是否存在一种选法，使得能恰好装满整个收藏瓶（即所有选中纸星星的总体积等于 $L_i$）？ 如果存在，请告诉他所有可行方案中，瓶中纸星星的美观程度之和的最大值；否则请告诉小 C 不存在这样的选法（输出 -1）。

输入格式

本题包含多组测试数据。

第一行包含一个正整数 $T$，表示数据组数。

接下来依次描述每组数据。对于每组数据：

• 第一行包含两个正整数 $n$ 和 $m$ —— 分别表示纸星星的个数和收藏瓶的个数。
• 第二行包含 $n$ 个正整数 $v_1, v_2, \dots, v_n$ —— 依次表示每颗纸星星的体积大小。
• 第三行包含 $n$ 个正整数 $b_1, b_2, \dots, b_n$ —— 依次表示每颗纸星星的美观程度。
• 第四行包含 $m$ 个正整数 $L_1, L_2, \dots, L_m$ —— 依次表示每个收藏瓶的容量体积。

输出格式

输出共 $T$ 行，依次表示每组数据的答案。

对于每组数据，输出一行 $m$ 个整数，相邻整数之间用一个空格隔开。第 $i$ 个整数表示：如果存在装满第 $i$ 个收藏瓶的方案，输出美观程度之和的最大值；否则输出 -1。

样例输入 1

2
5 2
1 2 2 1 2
5 11 9 3 8
5 6
5 2
2 2 2 2 2
10 20 30 40 50
19 15

样例输出 1

25 28
-1 -1

样例输入 2

2 
10 3 
1 1 1 1 1 1 2 2 1 2 
45 37 49 22 14 91 56 65 81 97 
2 19 15 
10 3 
2 1 1 2 1 2 1 1 2 2 
40 29 37 81 65 75 35 66 73 96 
19 1 5

样例输出 2

172 -1 -1 
-1 66 264

说明

样例解释

样例 $1$ 不符合下方测试数据范围分布中的特殊限制，但可以演示问题的基本过程，实际测试数据保证符合下方的数据范围分布

• 在第一组数据中：
  • 当 $L = 5$ 时，最优方案选择第 $1, 2, 3$ 颗纸星星，此时美观程度之和为 $5 + 11 + 9 = 25$。
  • 当 $L = 6$ 时，最优方案选择第 $2, 3, 5$ 颗纸星星，此时美观程度之和为 $11 + 9 + 8 = 28$。
• 在第二组数据中：所有星星的体积都为偶数（均为 $2$），但是收藏瓶的体积为奇数（$19$ 和 $15$），因此无论如何也无法恰好装满，不存在合法的方案。

其它样例说明

• 样例 $3$：见选手附加文件目录下的 star/star3.in 和 star/star3.ans。该组数据满足测试点 $4$ 的条件。
• 样例 $4$：见选手附加文件目录下的 star/star4.in 和 star/star4.ans。该组数据满足测试点 $8$ 的条件。

数据范围

对于所有数据，保证：

• $1 \le T \le 3$，
• $1 \le n \le 10^5$，
• $1 \le m, L_i \le 2n$，
• $1 \le v_i \le 2$，
• $1 \le b_i \le 10^6$。

保证所有的输入数值均为整数。

各测试点的附加限制如下表所示：

点击下载大样例