P13727 [GCPC 2024] Laundry

每个星期天都是洗衣日，总有一大堆衣服等着你去洗，这肯定会花掉你很长时间。 你尤其讨厌那些需要特别小心清洗的衣物，并且必须为每件衣物选择合适的洗涤程序。 :::align{center}  晾晒的衣服 [图片来自 gregroose，Pixabay](https://pixabay.com/photos/hanging-architecture-clothesline-3282769/) ::: 幸运的是，你的洗衣机很老旧，只支持三种不同的洗涤程序：A、B 和 C。 你每次最多可以在一桶中放入 $k$ 件衣物， 每一桶只能选择其中一种洗涤程序。 有些衣物很容易打理，可以随意放进任何一桶。 更精致的衣物则不能用某一种特定的程序洗，但可以用另外两种。 当然，最麻烦的衣物只能用一种特定的程序洗。 你已经将衣物分成了七堆，每堆中的衣物都可以用相同的程序组合来清洗，因此你知道每一堆的数量。 你需要计算，最少需要多少桶才能把所有衣物洗完？ :::align{center}  图 L.1：样例输入 2 的最优解示意图。左侧为七堆衣物，每堆对应一种程序组合。右侧为一种（可能的）最优解，每堆衣物都用一桶洗。每堆上的数字表示该桶中洗了多少件对应组合的衣物。特别地，最左侧的衣物用程序 A 洗，中间两堆用程序 B 洗，右侧两堆用程序 C 洗。因此总共需要五桶洗完所有衣物，这是最优的，因为总共有 15 件衣物。 :::

输入的第一行包含一个整数 $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 洗的衣物数量。

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

由 ChatGPT 4.1 翻译