Description

每个星期天都是洗衣日，总有一大堆衣服等着你去洗，这肯定会花掉你很长时间。 你尤其讨厌那些需要特别小心清洗的衣物，并且必须为每件衣物选择合适的洗涤程序。

:::align{center}

晾晒的衣服 图片来自 gregroose，Pixabay :::

幸运的是，你的洗衣机很老旧，只支持三种不同的洗涤程序：A、B 和 C。 你每次最多可以在一桶中放入 $k$ 件衣物， 每一桶只能选择其中一种洗涤程序。

有些衣物很容易打理，可以随意放进任何一桶。 更精致的衣物则不能用某一种特定的程序洗，但可以用另外两种。 当然，最麻烦的衣物只能用一种特定的程序洗。

你已经将衣物分成了七堆，每堆中的衣物都可以用相同的程序组合来清洗，因此你知道每一堆的数量。

你需要计算，最少需要多少桶才能把所有衣物洗完？

:::align{center}

图 L.1：样例输入 2 的最优解示意图。左侧为七堆衣物，每堆对应一种程序组合。右侧为一种（可能的）最优解，每堆衣物都用一桶洗。每堆上的数字表示该桶中洗了多少件对应组合的衣物。特别地，最左侧的衣物用程序 A 洗，中间两堆用程序 B 洗，右侧两堆用程序 C 洗。因此总共需要五桶洗完所有衣物，这是最优的，因为总共有 15 件衣物。 :::

Input Format

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。对于每个测试用例：

• 一行包含一个整数 $k$（$1\leq k\leq 10^9$），表示每桶最多可放入的衣物数量。
• 一行包含七个整数 $c_1, \ldots, c_7$（$0 \leq c_i \leq 10^9$），表示每种程序组合的衣物数量。整数的顺序为：A、B、C、AB、BC、AC、ABC。例如，$c_4$ 表示必须用程序 A 或 B 洗的衣物数量。

Output Format

对于每个测试用例，输出洗完所有衣物所需的最少桶数。

4
10
15 11 9 5 2 7 1
120
0 0 0 0 0 0 0
6
5 6 8 9 1 0 0
1213
295053681 137950336 87466375 956271897 344992260 31402049 988259763

6
0
6
2342454

1
3
1 2 1 3 3 2 3

5

Hint

由 ChatGPT 4.1 翻译