Gagamboy 是菲律宾当地的蜘蛛侠，但他遇到了一个小麻烦：他的蛛丝液用完了！

Gagamboy 需要 1kg 编号为 1 到 $r$ 的不同化学品，以便合成他的蛛丝液。他忙于在马尼拉大都会打击犯罪，没时间亲自去购买这些化学品，因此他打算在网上订购。Gagamboy 使用的电子商务应用程序上有 $c$ 个卖家，编号为 1 到 $c$，他们专门为化学爱好者提供服务。

他需要的所有 $r$ 种化学品在 $c$ 个卖家处都有库存，但价格可能不同。这些价格可以用成本矩阵 $A$ 表示，其中 $a_{i,j}$ 表示从卖家 $j$ 购买 1kg 化学品 $i$ 的价格。

此外，对于每个卖家，如果 Gagamboy 从该卖家处订购了任何数量（非零）的化学品，他必须支付一笔固定的运费，以便将装有该卖家所有化学品的包裹运送到他家。运费由向量 $d$ 给出，其中 $d_j$ 是从卖家 $j$ 购买任何化学品所需支付的运费。

Gagamboy 特别强调这是一个固定运费。无论你从某个卖家 $j$ 订购了多少种化学品（可能是一种、两种或全部等），该卖家的运费始终仅为 $d_j$。

给定 $A$ 和 $d$，请确定 Gagamboy 购买至少 1kg 每种 $r$ 类化学品的最低成本。共有 $T$ 组独立的测试用例。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来是 $T$ 组测试用例的描述。

每个测试用例的第一行包含两个空格分隔的整数 $r$ 和 $c$。

接下来有 $r$ 行，每行包含 $c$ 个空格分隔的整数。第 $i$ 行第 $j$ 列的值为 $a_{i,j}$。

最后一行包含 $c$ 个空格分隔的整数 $d_1, d_2, \dots, d_c$。

输出格式

输出一行，包含一个整数，表示可能的最低总成本。

数据范围

$1 \le T \le 10$ $1 \le r, c$ $r \times c \le 250$ $1 \le a_{i,j} \le 10^{15}$，对于每个 $(i, j)$。 $1 \le d_j \le 10^{15}$，对于每个 $j$。

样例

输入 1

2
3 5
1 3 5 7 9
5 7 9 1 3
9 1 3 5 7
4 3 2 3 4
4 3
1 2 4
2 3 1
4 1 2
3 2 1
2 4 4

输出 1

11
11

说明

在第一个测试用例中，一种最优解如下：

• 从卖家 2 购买化学品 1 和 3。价格为 $a_{1,2} = 3$ 和 $a_{3,2} = 1$。运费为 $d_2 = 3$。
• 从卖家 4 购买化学品 2。价格为 $a_{2,4} = 1$。运费为 $d_4 = 3$。

总花费为 $((3 + 1) + 3) + ((1) + 3) = 11$。