Adonis 龙是龙族伟大的领袖。传承龙族血脉是龙族的重要使命。因此，Adonis 决定每年选择一个特殊的日子进行龙蛋生产。今天就是这一天！

生产龙蛋并不容易，它需要收集各种精华，如土、水、风、火等。具体来说，生产一个龙蛋需要 $n$ 种精华，第 $i$ 种精华的需求量为 $a_i$。

为了提高效率，Adonis 雇佣了许多工龙为他收集不同的精华。工龙共有 $k$ 个等级，从 1 级到 $k$ 级。$i$ 级工龙每天能获得的精华量为 $2^{i-1}$，但每条工龙只能收集一种精华。Adonis 可以在开始时分配每条工龙收集哪种精华，但一旦分配就不能更改。

已知 $i$ 级工龙的数量为 $b_i$，Adonis 想知道在最优分配方案下，今天最多能生产多少个龙蛋。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^3$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 5 \times 10^4, 1 \le k \le 20$)，分别表示精华的种类数和工龙的最高等级。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示生产一个龙蛋所需的每种精华的数量。

每个测试用例的第三行包含 $k$ 个整数 $b_1, b_2, \dots, b_k$ ($1 \le b_i \le 10^9$)，表示每个等级的工龙数量。

保证所有测试用例的 $n$ 之和不超过 $5 \times 10^4$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示最多能生产的龙蛋数量。

样例

输入 1

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

输出 1

2
4
4
5
2
3

说明

以下是样例中第一个测试用例的一种可能分配方案：

1. 分配 3 条 1 级工龙收集第一种精华，日产量为 $3 \times 1 = 3$。
2. 分配 2 条 2 级工龙收集第二种精华，日产量为 $2 \times 2 = 4$。
3. 分配 1 条 1 级工龙、2 条 2 级工龙和 1 条 3 级工龙收集第三种精华，日产量为 $1 \times 1 + 2 \times 2 + 1 \times 4 = 9$。
4. 分配 3 条 3 级工龙收集第四种精华，日产量为 $3 \times 4 = 12$。

可生产的龙蛋数量为 $\min(\lfloor\frac{3}{1}\rfloor, \lfloor\frac{4}{2}\rfloor, \lfloor\frac{9}{3}\rfloor, \lfloor\frac{12}{4}\rfloor) = \min(3, 2, 3, 3) = 2$。