ЗАДАЧА C

Почта

Имя входного файла:post.in
Имя выходного файла:post.out
Ограничение по времени:1 секунда
Ограничение по памяти:64 Мб

Шарик достал уголёк и на боку печки стал рисовать домик.
– Эй, - спрашивает кот, – что это? Что это за народное творчество на моей печке?
– Это индейская национальная изба, – ехидно отвечает Шарик, – "фигвам" называется.
– Что? – кричит Матроскин. – Да я в него за это утюгом! Где мой утюг деревенский с углями?
Он притащил огромный чугунный утюг, прямо как из музея.
– Стоп-стоп! – говорит Печкин. – Это уже посылка получается. Платите двадцать рублей за доставку. Я уж ваш утюг передам.


Э.Успенский «Тетя дяди Федора», глава 9



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

Но прежде чем запустить (а точнее переслать почтой) в Шарика утюгом, экономный кот Матроскин призадумался. «Это что ж получается», – рассуждал он – «я на этого балбеса еще и деньги тратить должен! Если уж и так, то надо постараться потратить как можно меньше».

Кот хочет переслать N предметов, причем непременно в указанном порядке (на то есть очень важные политические причины). Коту в точности известен вес каждого из предметов в граммах. Почтальон Печкин может передавать предметы только письмом, бандеролью или посылкой. Стоимость письма составляет C1 рублей, а максимальный вес – G1 граммов. Для бандероли – C2 рублей и G2 граммов, а для посылки – C3 рублей и G3 граммов. В одном почтовом отправлении можно пересылать несколько подряд идущих предметов. Помогите коту Матроскину переслать все предметы в заданном порядке Шарику, потратив при этом как можно меньше денег.

Входные данные


Первая строка входного файла содержит единственное натуральное число N (1 <= N <= 1000) – количество предметов. Во второй строке перечислены N целых чисел Ai (1 <= Ai <= G3) – веса пересылаемых предметов в порядке их пересылки. Третья строка содержит 3 натуральных числа 0 < C1 < C2 < C3 <= 106 – стоимости письма, бандероли и посылки соответственно. Четвертая строка также содержит 3 натуральных числа 0 < G1 < G2 < G3 <= 106 – максимальный вес письма, бандероли и посылки соответственно в граммах.

Выходные данные


В выходной файл выведите единственное целое число – минимально возможную стоимость отправки всех предметов в заданном порядке Шарику.

Пример


post.in post.out 
3
12 998 20
15 20 50
20 40 1000
 
80