410464: GYM104023 I Dragon Bloodline

Adonis the Dragon is a great leader of the dragon kingdom. It is an important mission for the dragons to pass on the dragon bloodline. Therefore, Adonis decides to choose a special day each year for egg production. Today is the day!

It is not easy to produce a dragon egg, which needs to collect various kinds of essences such as earth, water, wind, fire, etc. Specifically, the production of a dragon egg requires $$$n$$$ kinds of essences, the amount for the $$$i$$$-th of which is $$$a_i$$$.

To improve efficiency, Adonis employs many worker dragons to collect different kinds of essences for him. There are $$$k$$$ different levels of worker dragons, from level $$$1$$$ to level $$$k$$$. The amount of essence that a worker dragon of level $$$i$$$ can obtain in one day is $$$2^{i-1}$$$, but each worker dragon can collect only one kind of essence. Adonis can assign which kind of essence each worker dragon should collect at the beginning, but it cannot be changed once assigned.

Knowing that the number of dragons of level $$$i$$$ is $$$b_i$$$, Adonis wants to know the maximum number of dragon eggs that can be produced today with the best assignment.

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10^3$$$), denoting the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 5 \times 10^4$$$, $$$1 \leq k \leq 20$$$), denoting the number of kinds of essences and the maximum level of worker dragons.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), denoting the amount of each kind of essence required to produce a dragon egg.

The third line of each test case contains $$$k$$$ integers $$$b_1, b_2 \dots, b_k$$$ ($$$1 \leq b_i \leq 10^9$$$), denoting the number of worker dragons of each level.

It is guaranteed that $$$\sum n \le 5 \times 10^4$$$ over all test cases.

For each test case, output an integer in a single line denoting the maximum number of dragon eggs that can be produced.

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

2
4
4
5
2
3

Here is one possible assignment for the first case of the sample:

1. Assign $$$3$$$ worker dragons of level $$$1$$$ to the first essence, with a daily production of $$$3\times1=3$$$.
2. Assign $$$2$$$ worker dragons of level $$$2$$$ to the second essence, with a daily production of $$$2\times2=4$$$.
3. Assign $$$1$$$ worker dragon of level $$$1$$$, $$$2$$$ worker dragons of level $$$2$$$, and $$$1$$$ worker dragon of level $$$3$$$ to the third essence, with a daily production of $$$1\times1+2\times2+1\times4=9$$$.
4. Assign $$$3$$$ worker dragons of level $$$3$$$ to the fourth essence, with a daily production of $$$3\times4=12$$$.

The number of dragon eggs that can be produced is $$$\min(\lfloor\dfrac{3}{1}\rfloor,\lfloor\dfrac{4}{2}\rfloor,\lfloor\dfrac{9}{3}\rfloor,\lfloor\dfrac{12}{4}\rfloor)=\min(3,2,3,3)=2$$$.