题目描述

请注意本题的特殊时间限制。

在 死鱼大陆 上，有一家享誉世界的制造集团 —— 死鱼工厂集团。
集团旗下共有 $m$ 座工厂，每座工厂位于不同城市，并且每天的产能有限：第 $j$ 座工厂 最多 可以接收 $b_j$ 件物品进行加工。

现在有 $n$ 件来自世界各地的物品等待加工。
由于这些物品的生产工艺极其复杂，第 $i$ 件物品必须被送往 恰好 $a_i$ 家 不同的工厂 同时加工，才能完成生产流程。
如果将第 $i$ 件物品送去第 $j$ 座工厂加工，可以带来价值提升 $w_{i,j}$。

你的任务是为所有物品制定一个加工分配方案，使得以下条件全部满足：

1. 每件物品恰好被分配到 $a_i$ 家 不同的工厂；
2. 每座工厂接收的物品数量不超过它的容量上限 $b_j$。

在满足上述条件的前提下，最大化所有分配的总价值提升 $\sum w_{i,j}$。
如果不存在满足条件的分配方案，使得所有物品都能完成加工，则输出 $-1$。

输入格式

第一行包含一个整数 $T$，表示测试用例的组数。

对于每组测试数据：

• 第一行包含两个整数 $n$ 和 $m$ ($1 \leq n, m \leq 500$)，分别表示物品数量和工厂数量。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ ($1 \leq a_i \leq 500$) 表示第 $i$ 件物品需要被分配到的工厂数量。
• 第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$，其中 $b_j$ ($1 \leq b_j \leq 500$) 表示第 $j$ 座工厂最多可以接收的物品数量。
• 接下来 $n$ 行，每行包含 $m$ 个整数，第 $i$ 行第 $j$ 个整数表示 $w_{i,j}$ ($1 \leq w_{i,j} \leq 10^9$)，即第 $i$ 件物品分配到第 $j$ 座工厂时的价值提升。

保证在一个测试点中，所有测试数据中 $b_j$ 的总和不超过 $500$。

输出格式

对于每组测试数据，输出一个整数，表示最大总价值提升。
如果无法满足所有物品的加工需求，输出 $-1$。

样例

2
6 6
1 1 4 5 1 4
1 9 1 9 8 10
1 4 1 3 5 6
2 3 5 3 2 2
3 4 5 3 6 2
2 4 7 8 4 1
1 8 9 5 3 4
5 6 9 3 2 2
2 4
9 9
1 9 2 6
8 17 1 1
1 1 1 1

72
-1