Bon2000

25.07.2021 02:50 •  Информатика

На пути к Мордору Фродо нужно преодолеть большую трясину. Участки трясины перемежаются небольшими участками суши. Фродо собирается попасть на другой берег трясины, прыгая по участкам суши. Примем, что размеры участков суши не имеют значения и расположены в ряд, причем расстояние между ними почти одинаковое.

Фродо может прыгнуть вперед на один, два или три участка суши. При этом он расходует силы. Прыгнув вперед на один участок суши, он потратит s1 сил, на два – s2 сил, на три – s3 сил.

У Фродо остались эльфийские питательные хлебцы-путлибы, которые восстанавливают силы. Но в дороге они раскрошились на кусочки разного веса (вес кусочка – целое число). По счастливой случайности количество кусочков совпадает с количеством участков суши на пути Фродо. Примем, что перед тем, как сделать прыжок, Фродо съедает один кусочек путлиба, причем выбор веса кусочка не зависит от Фродо.

Задача Фродо – попасть на другой берег трясины и при этом накопить как можно больше сил. Сколько сил он сможет накопить? Нужно учитывать, что Фродо не может прыгать, если его силы закончились, и он не сможет допрыгнуть до следующего участка суши, если расстояние до него больше, чем у него осталось сил.

Формат входных данных

В первой строке записано число N – количество участков суши в трясине (2 ≤ N ≤ 1000).

Затем идет N целых чисел vi, записанных в одной строке – вес каждого кусочка путлиба (0 ≤ vi ≤ 100). В начальный момент времени Фродо находится на первом участке суши и может спокойно съесть кусочек путлиба.

В третьей строке записано 3 целых числа: s1, s2, s3 – количество сил, которое необходимо затратить на прыжок на один участок суши (s1) вперед, на два (s2) и на три (s3). (1 ≤ s1 ≤ s2 ≤ s3 ≤ 100).

Формат выходных данных

Выведите одно целое число – максимальное количество сил, которое будет у Фродо, когда он окажется на последнем участке суши. Не забудьте добавить к этому числу вес последнего кусочка путлиба.

Если Фродо не сможет добраться до конца, выведите -1.

Примеры

Замечание

В первом тесте перед первым прыжком Фродо съест кусочек путлиба весом 5 единиц, перепрыгнет на второй участок суши (потратит 2 единицы силы) и съест кусочек путлиба на втором участке суши (у него станет 5 -2 + 4 = 7 единиц силы), затем перепрыгнет на третий участок и съест кусочек там (7 - 2 + 1 = 6 единиц силы), затем перепрыгнет на четвертый (6 - 2 + 6 = 10) и наконец окажется на последнем участке (10 -2 + 1 = 9).

Во втором тесте перед первым прыжком Фродо съест путлиб на первом участке суши (5), перепрыгнет на второй (потратит 3 единицы силы) и съест кусок путлиба на втором участке (у него станет 5 - 3 + 4 = 6 единиц силы), а затем перепрыгнет сразу на четвертый (6 - 4 + 6 = 8) и наконец, окажется на последнем участке суши (8 - 3 + 1 = 6).

В третьем тесте Фродо не сможет добраться до последнего участка суши