CF85B Embassy Queue

在一个著名王国的大使馆中，设置了电子排队系统。每个来办事的人都需要完成以下三个操作：出示身份证、向收银员付款以及按指纹。这些操作必须按照给定的顺序依次完成。 每个操作分别有若干个独立窗口：第一项操作有 $k_{1}$ 个窗口（第 1 类窗口），第二项操作有 $k_{2}$ 个窗口（第 2 类窗口），第三项操作有 $k_{3}$ 个窗口（第 3 类窗口）。在任何一个第 1 类窗口为一个人服务的时间为 $t_{1}$，第 2 类窗口为 $t_{2}$，第 3 类窗口为 $t_{3}$。因此，服务时间只取决于窗口类型，与申请签证的人没有关系。 在某一时刻，有 $n$ 个人来到大使馆，第 $i$ 个人来的时刻为 $c_{i}$。人被登记后会取到一个编号，然后坐在大厅中等待，直到自己的编号被显示在电子屏幕上。除了本人编号外，屏幕还会显示需要前往的窗口编号，此人会立即前往，所需时间可以忽略。显示屏每次只能显示一个人的信息。电子排队系统保证每当某人到达窗口后能立刻开始办理业务，因为窗口前没有其他人排队。 顾客服务质量监察员发现有些人在大使馆里等待的时间过长（尤其令人疲惫，因为馆内没有手机信号和 3G 网络）。决定重新优化系统，使得人在大使馆内的最长逗留时间尽可能最小。请你帮助监察员设计最优的排队方案。假设所有除了在窗口办理业务外的操作都是瞬时完成的。

第一行包含三个用空格分隔的整数 $k_{1}$、$k_{2}$、$k_{3}$（$1 \leq k_{i} \leq 10^{9}$），分别表示第 1、2、3 类窗口的数量。 第二行包含三个用空格分隔的整数 $t_{1}$、$t_{2}$、$t_{3}$（$1 \leq t_{i} \leq 10^{5}$），分别表示第 1、2、3 类窗口为一个人服务所需的时间。 第三行包含一个整数 $n$（$1 \leq n \leq 10^{5}$），表示前来大使馆的人数。 第四行包含 $n$ 个用空格分隔的整数 $c_{i}$（$1 \leq c_{i} \leq 10^{9}$），按非递减顺序排列，$c_{i}$ 表示第 $i$ 个人到达大使馆的时刻。

输出一个整数，表示在最优排队方案下，人员在大使馆内逗留的最长时间。 请不要在 C++ 中使用 %lld 读写 64 位整数。建议使用 cin、cout (你也可以使用 %I64d)。

在第一个测试点中，5 个人在时间 1 同时到达，每种类型的窗口只有 1 个，每个窗口办理业务时间为 1。所以，一个人在大使馆内花费的最长时间为窗口办理（3 个单位时间）加上最后一位等候办理第一个窗口的等待时间（4 个单位时间）。 第二个测试点中各窗口工作安排如下： 第 1 类第 1 个窗口： $[1,6)$ — 第 1 人，$[6,11)$ — 第 3 人，$[11,16)$ — 第 5 人 第 1 类第 2 个窗口： $[2,7)$ — 第 2 人，$[7,12)$ — 第 4 人 唯一的第 2 类窗口：$[6,7)$ — 第 1 人，$[7,8)$ — 第 2 人，$[11,12)$ — 第 3 人，$[12,13)$ — 第 4 人，$[16,17)$ — 第 5 人 唯一的第 3 类窗口：$[7,8)$ — 第 1 人，$[8,9)$ — 第 2 人，$[12,13)$ — 第 3 人，$[13,14)$ — 第 4 人，$[17,18)$ — 第 5 人 可以看出，第 5 个人的总办理耗时最长。 由 ChatGPT 5 翻译