B. Очередь в посольстве
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

В посольстве одного немалоизвестного королевства организована электронная очередь. Каждому человеку, пришедшему в посольство, необходимо выполнить следующие три действия: подать документы, заплатить деньги в кассу и сдать отпечатки пальцев. При этом действия должны выполняться именно в указанном порядке.

Для каждого действия отведено несколько отдельных окон: k1 различных окон для первого действия, k2 для второго, и k3 для третьего. Время обслуживания одного человека в окне каждом из k1 окон для первого действия равно t1. Аналогично, время обслуживания одного человека в каждом из k2 окон для второго действия равно t2, а время обслуживания одного человека в каждом из k3 окон для третьего действия равно 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 для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout (также вы можете использовать спецификатор %I64d).

Примеры
Входные данные
1 1 1
1 1 1
5
1 1 1 1 1
Выходные данные
7
Входные данные
2 1 1
5 1 1
5
1 2 3 3 5
Выходные данные
13
Примечание

В первом тесте 5 человек приходят одновременно в момент времени 1. Каждого типа по одному окну, каждое окно обслуживает 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) — пятый

Видно, что дольше всех обслуживается пятый человек.