#P14125. [SCCPC 2021] Monster Hunter

[SCCPC 2021] Monster Hunter

题目描述

Ema is the best carry player in a game. In the game, she needs to eliminate mm monsters. The ii-th monster has hih_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 00, the monster is eliminated.

To make the game more interesting, the attack power is not a constant number. There is a basic attack sequence a1,a2,,ana_1, a_2, \cdots, a_n, and the damage caused is generated by repeating this sequence. Formally, let rir_i be the damage caused by the ii-th attack, we have

$$r_{i}= \left \{ \begin{array}{ll} a_i & 1 \le i \le n \\ r_{i - n} & i > n \end{array} \right. $$

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?

输入格式

There are multiple test cases. The first line of the input contains an integer TT indicating the number of test cases. For each test case:

The first line contains an integer nn (1n1051 \le n \le 10^5) indicating the length of the basic attack sequence.

The second line contains nn integers a1,a2,,ana_1, a_2, \cdots, a_n (1ai31 \le a_i \le 3) indicating the basic attack sequence.

The third line contains an integer mm (1m1051 \le m \le 10^5) indicating the number of monsters.

The fourth line contains mm integers h1,h2,,hmh_1, h_2, \cdots, h_m (1hi1091 \le h_i \le 10^9) where hih_i indicates the initial HP of the ii-th monster.

It's guaranteed that neither the sum of nn nor the sum of mm of all test cases will exceed 10510^5.

输出格式

For each test case output one line containing one integer indicating the minimum number of attacks to eliminate all the monsters.

2
2
3 2
3
2 4 2
5
1 2 3 2 1
2
3 3
4
3

提示

For the first example, the damage sequence is 3,2,3,2,3,2,3, 2, 3, 2, 3, 2, \cdots. We can attack monsters 1, 2, 3 and 2 in order to eliminate all the 33 monsters.

For the second example, we can attack monsters 2, 2, 1 in order.