← 返回题目列表

Codeforces · 85/B

B. 使馆队列

中文机器翻译题面 查看原题

在一个著名王国的大使馆里组织了一个电子队列。每个来到使馆的人,都需要进行以下三个动作:出示身份证件、向收银员付款、采集指纹。此外,操作应按给定的顺序执行。

对于每个动作,挑选出几个单独的窗口:第一个动作的 k1 个单独的窗口(第一种类型窗口),第二个动作的 k2 个窗口(第二种类型窗口),以及第三个动作的 k3 个窗口(第三类窗口)。任一第一类窗口中一个人的服务时间等于t1。类似地,在任何第二类窗口中为一个人提供服务需要t2时间。在任何第三类窗口中为一个人服务需要 t3。因此,服务时间仅取决于窗口类型,与申请签证的人无关。

在某个时刻,有 n 个人来到大使馆,第 i 个人在时间 ci 到来。该人已登记在某个号码下。之后,他坐在大厅里,等待他的号码显示在一个特殊的板上。除了该人的号码外,板上还显示了该人应该去的窗口的号码,该人立即前往那里。让我们考虑一下接近窗口所需的时间可以忽略不计。该表一次最多只能显示一个人的信息。由于窗前没有其他人,电子排队系统会立即开始处理接近窗口的人。

客服质检员注意到,有几个人在使馆待的时间太长(特别烦人,因为使馆没有手机信号和3G)。我们决定组织这个系统,使一个人在大使馆停留的时间尽可能短。帮助检查人员整理队列。考虑一下除了在窗口送达之外的所有操作都会立即发生。

输入

第一行包含三个空格分隔的整数k1、k2、k3(1≤ki≤109),它们分别是第一、第二、第三类窗口的数量。

第二行包含三个空格分隔的整数t1、t2、t3(1≤ti≤105),分别是在第一、第二、第三类窗口中为一个人服务所需的时间段。

第三行包含一个整数n(1≤n≤105),它是人数。

第四行包含n个以空格分隔的非降序整数ci (1 ≤ ci ≤ 109); ci 是号码 i 到达使馆的时间。

输出

打印单个数字,即在最佳队列组织情况下,一个人在大使馆停留的最长时间。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流(您也可以使用 %I64d 说明符)。

示例

输入 #1

1 1 1
1 1 1
5
1 1 1 1 1

输出 #1

7

输入 #2

2 1 1
5 1 1
5
1 2 3 3 5

输出 #2

13

注意

第一个测试中,5个人在时间等于1的时刻同时到来。每种类型有一个窗口,每个窗口需要1个时间单位来服务。这就是为什么一个人在大使馆停留的最长时间是在窗口需要服务的时间(3个单位时间)加上最后一个来到第一个窗口的人等待的时间(4个单位时间)。

Windows 在第二次测试中的工作方式如下:

第一类第一个窗口:[1, 6) — 第一人称,[6, 11) — 第三人称,[11, 16) — 第五人称

第一种类型的第二个窗口:[2, 7) — 第二人,[7, 12) — 第四人

唯一的第二类窗口:[6, 7) — 第一,[7, 8) — 第二,[11, 12) — 第三,[12, 13) — 第四,[16, 17) — 第五]

唯一的第三类窗口:[7, 8) — 第一,[8, 9) — 第二,[12, 13) — 第三,[13, 14) — 第四,[17, 18) — 第五]

我们可以看到,服务第五个人花费的时间最多。