P14125 [SCCPC 2021] Monster Hunter

Ema 是游戏中最强的“carry”玩家。在游戏里，她需要消灭 $m$ 个怪物。第 $i$ 个怪物初始有 $h_i$ 点生命值（HP）。每当 Ema 攻击一个怪物时，该怪物的生命值会减少她的攻击力。当怪物的生命值小于等于 $0$ 时，该怪物就会被消灭。 为了让游戏更加有趣，Ema 的攻击力不是一个固定值。她有一个基础攻击力序列 $a_1, a_2, \cdots, a_n$，伤害值是不断重复该序列获得的。形式化地，设第 $i$ 次攻击造成的伤害为 $r_i$，则有 $$ r_{i}= \left \{ \begin{array}{ll} a_i & 1 \leq i \leq n \\ r_{i - n} & i > n \end{array} \right. $$ 为了尽快消灭怪物，Ema 想要攻击次数尽量少。你能帮助她计算消灭所有怪物所需的最少攻击次数吗？

有多组测试数据。输入的第一行为一个整数 $T$，表示测试组数。对于每组测试数据： 第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示基础攻击力序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \leq a_i \leq 3$），表示基础攻击力序列。 第三行包含一个整数 $m$（$1 \leq m \leq 10^5$），表示怪物的数量。 第四行包含 $m$ 个整数 $h_1, h_2, \cdots, h_m$（$1 \leq h_i \leq 10^9$），其中 $h_i$ 表示第 $i$ 个怪物的初始生命值。 保证所有测试用例中 $n$ 的和及 $m$ 的和均不超过 $10^5$。

对于每组测试数据，输出一行一个整数，表示消灭所有怪物所需的最少攻击次数。

对于第一个样例，伤害序列为 $3, 2, 3, 2, 3, 2, \cdots$。可以按顺序依次攻击怪物 $1$、$2$、$3$、$2$，就可以消灭所有 $3$ 个怪物。 对于第二个样例，可以依次攻击怪物 $2$、$2$、$1$。 由 ChatGPT 5 翻译