题目描述

Dave 是一名出色的游戏玩家，他这次需要在游戏中消灭 $m$ 只怪物来通关，第 $i$ 只怪物的血量为 $h_i$。当一只怪物的血量降到 $0$ 或 $0$ 以下，那么这只怪物就被消灭了。

与其他游戏类似，Dave 可以使用技能对怪物造成伤害，为了让游戏更有趣，每次技能造成的伤害并不相同。具体地，游戏内置了一个技能强度序列 $a_{1\cdots n}$，Dave 第 $i$ 次攻击造成的伤害即为 $a_{((i-1)\bmod n)+1}$，即伤害数值以 $n$ 次技能为一个周期循环，而 Dave 也提前知道这个技能强度序列的所有信息。

为了尽快消灭所有怪物，Dave 想知道最少多少次攻击能够通关。

输入格式

第一行一个整数 $T$ 表示数据组数，对于每组数据：

第一行一个整数 $n$，表示技能强度序列长度。

第二行 $n$ 个整数 $a_{1\cdots n}$ 表示技能强度序列。

第三行一个整数 $m$，表示怪物数量。

第四行 $m$ 个整数 $h_{1\cdots m}$ 表示怪物血量。

输出格式

对于每组数据，输出一行一个整数表示最小攻击次数。

1
3
2 2 2
3
1 2 2

3

样例解释 1

以任意顺序攻击存活的怪物即可。

数据范围

对于 $30\%$ 的数据，$T=1$，$n,m,h_i\leq 3$。

对于 $60\%$ 的数据，$T=1$，$\sum n,\sum m\leq 10^3$，$h_i\leq 6$。

对于 $100\%$ 的数据，$1\leq T\leq 10^4$，$1\leq n\leq \sum n\leq 10^5$，$1\leq m\leq \sum m\leq 10^5$，$1\leq a_i\leq 3$，$1\leq h_i\leq 10^9$。