{"raw_statement":[{"iden":"statement","content":"In an embassy of a well-known kingdom an electronic queue is organised. Every person who comes to the embassy, needs to make the following three actions: show the ID, pay money to the cashier and be fingerprinted. **Besides, the actions should be performed in the given order.**\n\nFor each action several separate windows are singled out: _k_1 separate windows for the first action (the first type windows), _k_2 windows for the second one (the second type windows), and _k_3 for the third one (the third type windows). The service time for one person in any of the first type window equals to _t_1. Similarly, it takes _t_2 time to serve a person in any of the second type windows. And it takes _t_3 to serve one person in any of the third type windows. Thus, the service time depends only on the window type and is independent from the person who is applying for visa.\n\nAt some moment _n_ people come to the embassy, the _i_\\-th person comes at the moment of time _c__i_. The person is registered under some number. After that he sits in the hall and waits for his number to be shown on a special board. Besides the person's number the board shows the number of the window where one should go and the person goes there immediately. Let's consider that the time needed to approach the window is negligible. The table can show information for no more than one person at a time. The electronic queue works so as to immediately start working with the person who has approached the window, as there are no other people in front of the window.\n\nThe Client Service Quality inspectors noticed that several people spend too much time in the embassy (this is particularly tiresome as the embassy has no mobile phone reception and 3G). It was decided to organise the system so that the largest time a person spends in the embassy were minimum. Help the inspectors organise the queue. Consider that all actions except for being served in at the window, happen instantly."},{"iden":"input","content":"The first line contains three space-separated integers _k_1, _k_2, _k_3 (1 ≤ _k__i_ ≤ 109), they are the number of windows of the first, second and third type correspondingly.\n\nThe second line contains three space-separated integers _t_1, _t_2, _t_3 (1 ≤ _t__i_ ≤ 105), they are the periods of time needed to serve one person in the window of the first, second and third type correspondingly.\n\nThe third line contains an integer _n_ (1 ≤ _n_ ≤ 105), it is the number of people.\n\nThe fourth line contains _n_ space-separated integers _c__i_ (1 ≤ _c__i_ ≤ 109) in the non-decreasing order; _c__i_ is the time when the person number _i_ comes to the embassy."},{"iden":"output","content":"Print the single number, the maximum time a person will spend in the embassy if the queue is organized optimally.\n\nPlease, do not use the _%lld_ specificator to read or write 64-bit integers in C++. It is preferred to use the _cin_, _cout_ streams (also you may use the _%I64d_ specificator)."},{"iden":"examples","content":"Input\n\n1 1 1\n1 1 1\n5\n1 1 1 1 1\n\nOutput\n\n7\n\nInput\n\n2 1 1\n5 1 1\n5\n1 2 3 3 5\n\nOutput\n\n13"},{"iden":"note","content":"In the first test 5 people come simultaneously at the moment of time equal to 1. There is one window of every type, it takes 1 unit of time to be served at each window. That's why the maximal time a person spends in the embassy is the time needed to be served at the windows (3 units of time) plus the time the last person who comes to the first window waits (4 units of time).\n\nWindows in the second test work like this:\n\nThe first window of the first type: \\[1, 6) — the first person, \\[6, 11) — third person, \\[11, 16) — fifth person\n\nThe second window of the first type: \\[2, 7) — the second person, **\\[7, 12)** — the fourth person\n\nThe only second type window: \\[6, 7) — first, \\[7, 8) — second, \\[11, 12) — third, \\[12, 13) — fourth, \\[16, 17) — fifth\n\nThe only third type window: \\[7, 8) — first, \\[8, 9) — second, \\[12, 13) — third, \\[13, 14) — fourth, \\[17, 18) — fifth\n\nWe can see that it takes most time to serve the fifth person."}],"translated_statement":[{"iden":"statement","content":"在某个知名王国的大使馆中，组织了一个电子排队系统。每个前来大使馆的人需要完成以下三个步骤：出示身份证、向出纳付款、进行指纹识别。*此外，这些步骤必须按给定顺序执行。*\n\n对于每个步骤，都设有若干独立的窗口：第一个步骤设有 #cf_span[k1] 个窗口（第一类窗口），第二个步骤设有 #cf_span[k2] 个窗口（第二类窗口），第三个步骤设有 #cf_span[k3] 个窗口（第三类窗口）。在任意一个第一类窗口中，服务一个人所需的时间为 #cf_span[t1]。类似地，在任意一个第二类窗口中，服务一个人需要 #cf_span[t2] 的时间；在任意一个第三类窗口中，服务一个人需要 #cf_span[t3] 的时间。因此，服务时间仅取决于窗口类型，与申请签证的人无关。\n\n在某一时刻，有 #cf_span[n] 个人来到大使馆，第 #cf_span[i] 个人在时间 #cf_span[ci] 到达。每个人被分配一个编号，随后在大厅中等候，直到他的编号在一块专用屏幕上显示。屏幕除了显示人员编号外，还会显示应前往的窗口编号，人员随即立即前往该窗口。假设前往窗口所需的时间可忽略不计。屏幕每次仅能显示一个人的信息。电子排队系统的设计原则是：一旦有人到达窗口，就立即开始服务，因为窗口前没有其他人。\n\n客户服务品质检查员发现，有若干人花费了过多时间在大使馆内（尤其令人疲惫，因为大使馆内没有手机信号和3G）。因此决定优化系统，使得任何人花费在大使馆内的最长时间最小化。请帮助检查员组织排队系统。假设除在窗口接受服务外，其他所有操作均瞬间完成。\n\n第一行包含三个用空格分隔的整数 #cf_span[k1], #cf_span[k2], #cf_span[k3]（#cf_span[1 ≤ ki ≤ 10^9]），分别表示第一类、第二类和第三类窗口的数量。\n\n第二行包含三个用空格分隔的整数 #cf_span[t1], #cf_span[t2], #cf_span[t3]（#cf_span[1 ≤ ti ≤ 10^5]），分别表示在第一类、第二类和第三类窗口中服务一个人所需的时间。\n\n第三行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]），表示人数。\n\n第四行包含 #cf_span[n] 个按非递减顺序排列的空格分隔整数 #cf_span[ci]（#cf_span[1 ≤ ci ≤ 10^9]）；#cf_span[ci] 表示第 #cf_span[i] 个人到达大使馆的时间。\n\n请输出一个数字，表示在最优排队组织下，一个人在大使馆内花费的最长时间。\n\n请注意，在 C++ 中请勿使用 _%lld_ 标识符读写 64 位整数。推荐使用 _cin_、_cout_ 流（也可使用 _%I64d_ 标识符）。\n\n在第一个测试用例中，5 个人同时在时间 1 到达。每种类型各有一个窗口，每个窗口服务一个人需 1 单位时间。因此，一个人在大使馆内花费的最长时间等于在三个窗口的服务时间（3 单位时间）加上最后一个到达第一类窗口的人所等待的时间（4 单位时间）。\n\n第二个测试用例中窗口的工作方式如下：\n\n第一个第一类窗口：#cf_span[[1, 6)] — 第一个人，#cf_span[[6, 11)] — 第三个人，#cf_span[[11, 16)] — 第五个人\n\n第二个第一类窗口：#cf_span[[2, 7)] — 第二个人，*#cf_span[[7, 12)]* — 第四个人\n\n唯一的第二类窗口：#cf_span[[6, 7)] — 第一个人，#cf_span[[7, 8)] — 第二个人，#cf_span[[11, 12)] — 第三个人，#cf_span[[12, 13)] — 第四个人，#cf_span[[16, 17)] — 第五个人\n\n唯一的第三类窗口：#cf_span[[7, 8)] — 第一个人，#cf_span[[8, 9)] — 第二个人，#cf_span[[12, 13)] — 第三个人，#cf_span[[13, 14)] — 第四个人，#cf_span[[17, 18)] — 第五个人\n\n可以看出，第五个人花费的时间最长。"},{"iden":"input","content":"第一行包含三个用空格分隔的整数 #cf_span[k1], #cf_span[k2], #cf_span[k3]（#cf_span[1 ≤ ki ≤ 10^9]），分别表示第一类、第二类和第三类窗口的数量。第二行包含三个用空格分隔的整数 #cf_span[t1], #cf_span[t2], #cf_span[t3]（#cf_span[1 ≤ ti ≤ 10^5]），分别表示在第一类、第二类和第三类窗口中服务一个人所需的时间。第三行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]），表示人数。第四行包含 #cf_span[n] 个按非递减顺序排列的空格分隔整数 #cf_span[ci]（#cf_span[1 ≤ ci ≤ 10^9]）；#cf_span[ci] 表示第 #cf_span[i] 个人到达大使馆的时间。"},{"iden":"output","content":"请输出一个数字，表示在最优排队组织下，一个人在大使馆内花费的最长时间。请注意，在 C++ 中请勿使用 _%lld_ 标识符读写 64 位整数。推荐使用 _cin_、_cout_ 流（也可使用 _%I64d_ 标识符）。"},{"iden":"examples","content":"输入\n1 1 1\n1 1 1\n5\n1 1 1 1 1\n输出\n7\n\n输入\n2 1 1\n5 1 1\n5\n1 2 3 3 5\n输出\n13"},{"iden":"note","content":"在第一个测试用例中，5 个人同时在时间 1 到达。每种类型各有一个窗口，每个窗口服务一个人需 1 单位时间。因此，一个人在大使馆内花费的最长时间等于在三个窗口的服务时间（3 单位时间）加上最后一个到达第一类窗口的人所等待的时间（4 单位时间）。第二个测试用例中窗口的工作方式如下：\n\n第一个第一类窗口：#cf_span[[1, 6)] — 第一个人，#cf_span[[6, 11)] — 第三个人，#cf_span[[11, 16)] — 第五个人\n\n第二个第一类窗口：#cf_span[[2, 7)] — 第二个人，*#cf_span[[7, 12)]* — 第四个人\n\n唯一的第二类窗口：#cf_span[[6, 7)] — 第一个人，#cf_span[[7, 8)] — 第二个人，#cf_span[[11, 12)] — 第三个人，#cf_span[[12, 13)] — 第四个人，#cf_span[[16, 17)] — 第五个人\n\n唯一的第三类窗口：#cf_span[[7, 8)] — 第一个人，#cf_span[[8, 9)] — 第二个人，#cf_span[[12, 13)] — 第三个人，#cf_span[[13, 14)] — 第四个人，#cf_span[[17, 18)] — 第五个人\n\n可以看出，第五个人花费的时间最长。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ k_1, k_2, k_3 \\in \\mathbb{Z}^+ $ be the number of windows for each of the three stages.  \nLet $ t_1, t_2, t_3 \\in \\mathbb{Z}^+ $ be the service times per window for each stage.  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of people.  \nLet $ c_i \\in \\mathbb{Z}^+ $ be the arrival time of person $ i $, with $ c_1 \\leq c_2 \\leq \\dots \\leq c_n $.  \n\nEach person must pass through three sequential stages:  \n- Stage 1: Use one of $ k_1 $ windows with service time $ t_1 $.  \n- Stage 2: Use one of $ k_2 $ windows with service time $ t_2 $.  \n- Stage 3: Use one of $ k_3 $ windows with service time $ t_3 $.  \n\nA person cannot begin stage $ j+1 $ until they have completed stage $ j $, and each window can serve only one person at a time.\n\n**Constraints**  \n1. $ 1 \\leq k_1, k_2, k_3 \\leq 10^9 $  \n2. $ 1 \\leq t_1, t_2, t_3 \\leq 10^5 $  \n3. $ 1 \\leq n \\leq 10^5 $  \n4. $ 1 \\leq c_i \\leq 10^9 $, and $ c_i \\leq c_{i+1} $  \n\n**Objective**  \nMinimize the maximum total time spent in the embassy over all people, i.e., minimize:  \n$$\n\\max_{1 \\leq i \\leq n} \\left( \\text{completion time of stage 3 for person } i - c_i \\right)\n$$  \nby optimally assigning people to available windows at each stage, respecting sequential constraints and non-preemptive service.","simple_statement":null,"has_page_source":false}