Problem C
Monster Hunter
Ema is the best carry player in a game. In the game, she needs to eliminate $m$ monsters. The $i$-th monster has $h_ i$ health points (HP) at the beginning. When a monster is attacked by Ema, its HP is reduced by her attack power. When the HP of a monster is less than or equal to $0$, the monster is eliminated.
To make the game more interesting, the attack power is not a constant number. There is a basic attack sequence $a_1, a_2, \cdots , a_ n$, and the damage caused is generated by repeating this sequence. Formally, let $r_ i$ be the damage caused by the $i$-th attack, we have
\begin{align*} \begin{split} r_{i}= \left\{ \begin{array}{ll} a_ i & 1 \le i \le n \\ r_{i - n} & i > n \end{array} \right. \end{split}\end{align*}To eliminate the monsters as soon as possible, Ema wants to minimize the number of attacks. Can you tell her the minimum number of attacks required to eliminate all the monsters?
Input
There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. Each test case is described with four lines:
-
The first line of each test case contains an integer $n$ ($1 \le n \le 10^5$) indicating the length of the basic attack sequence.
-
The second line of each test case contains $n$ integers $a_1, a_2, \cdots , a_ n$ ($1 \le a_ i \le 3$) indicating the basic attack sequence.
-
The third line of each test case contains an integer $m$ ($1 \le m \le 10^5$) indicating the number of monsters.
-
The fourth and final line of each test case contains $m$ integers $h_1, h_2, \cdots , h_ m$ ($1 \le h_ i \le 10^9$) where $h_ i$ indicates the initial HP of the $i$-th monster.
It is guaranteed that neither the sum of $n$ nor the sum of $m$ over all test cases will exceed $10^5$.
Output
For each test case output one line containing one integer indicating the minimum number of attacks to eliminate all the monsters.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 2 3 2 3 2 4 2 5 1 2 3 2 1 2 3 3 |
4 3 |