Embassy Queue

유명한 왕국의 한 대사관에서는 전자 대기열을 운영한다. 대사관에 오는 모든 사람은 다음 세 가지 절차를 수행해야 한다. ID를 제시하고, 출납원에게 돈을 내고, 지문을 채취한다. 또한 이 절차들은 주어진 순서대로 수행해야 한다.

각 절차를 위해 여러 개의 창구가 별도로 마련되어 있다. 첫 번째 절차에는 k1개의 별도 창구(첫 번째 유형 창구), 두 번째 절차에는 k2개의 창구(두 번째 유형 창구), 세 번째 절차에는 k3개의 창구(세 번째 유형 창구)가 있다. 첫 번째 유형의 어느 창구에서든 한 사람을 처리하는 시간은 t1이다. 마찬가지로 두 번째 유형의 어느 창구에서든 한 사람을 처리하는 데 t2의 시간이 걸린다. 세 번째 유형의 어느 창구에서든 한 사람을 처리하는 데는 t3이 걸린다. 따라서 처리 시간은 창구 유형에만 의존하며 비자를 신청하는 사람과는 무관하다.

어느 시점에 n명이 대사관에 오며, i-th 사람은 시각 ci에 온다. 이 사람은 어떤 번호로 등록된다. 그 후 홀에 앉아 자신의 번호가 특별한 전광판에 표시되기를 기다린다. 전광판에는 그 사람의 번호와 함께 가야 할 창구 번호가 표시되며, 그 사람은 즉시 그곳으로 간다. 창구까지 가는 데 필요한 시간은 무시할 수 있다고 하자. 전광판은 한 번에 최대 한 사람의 정보만 표시할 수 있다. 창구 앞에는 다른 사람이 없으므로, 전자 대기열은 창구에 도착한 사람의 처리를 즉시 시작하도록 작동한다.

The Client Service Quality 조사관들은 몇몇 사람이 대사관에서 너무 많은 시간을 보낸다는 사실을 알아차렸다(대사관에서는 휴대전화 통신과 3G가 되지 않으므로 특히 고역이다). 한 사람이 대사관에서 보내는 시간의 최댓값이 최소가 되도록 시스템을 운영하기로 했다. 조사관들이 대기열을 운영할 수 있도록 도와주자. 창구에서 처리받는 것을 제외한 모든 절차는 즉시 이루어진다고 간주한다.

첫째 줄에는 공백으로 구분된 세 정수 k1, k2, k3 (1 ≤ ki ≤ 109)가 주어지며, 각각 첫 번째, 두 번째, 세 번째 유형의 창구 수이다.

둘째 줄에는 공백으로 구분된 세 정수 t1, t2, t3 (1 ≤ ti ≤ 105)가 주어지며, 각각 첫 번째, 두 번째, 세 번째 유형의 창구에서 한 사람을 처리하는 데 필요한 시간이다.

셋째 줄에는 정수 n (1 ≤ n ≤ 105)가 주어지며, 사람의 수이다.

넷째 줄에는 비내림차순으로 정렬된, 공백으로 구분된 n개의 정수 ci (1 ≤ ci ≤ 109)가 주어진다. ci는 번호가 i인 사람이 대사관에 오는 시각이다.

대기열을 최적으로 운영했을 때 한 사람이 대사관에서 보내는 시간의 최댓값인 하나의 수를 출력한다.

C++에서 64비트 정수를 읽거나 쓸 때 %lld 지정자를 사용하지 말라. cin, cout 스트림을 사용하는 것이 권장된다(%I64d 지정자를 사용해도 된다).

첫 번째 테스트에서는 시각이 1인 순간에 5명이 동시에 온다. 각 유형의 창구가 하나씩 있으며, 각 창구에서 처리받는 데 시간 1단위가 걸린다. 따라서 한 사람이 대사관에서 보내는 시간의 최댓값은 창구들에서 처리받는 데 필요한 시간(시간 3단위)에 첫 번째 창구에 마지막으로 오는 사람이 기다리는 시간(시간 4단위)을 더한 값이다.

두 번째 테스트의 창구들은 다음과 같이 작동한다.

첫 번째 유형의 첫 번째 창구: [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) — 다섯 번째 사람

다섯 번째 사람을 처리하는 데 가장 많은 시간이 걸린다는 것을 알 수 있다.