На пути к Мордору Фродо нужно преодолеть большую трясину. Участки трясины перемежаются небольшими участками суши. Фродо собирается попасть на другой берег трясины, прыгая по участкам суши. Примем, что размеры участков суши не имеют значения и расположены в ряд, причем расстояние между ними почти одинаковое.
Фродо может прыгнуть вперед на один, два или три участка суши. При этом он расходует силы. Прыгнув вперед на один участок суши, он потратит 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).
В третьем тесте Фродо не сможет добраться до последнего участка суши
ответ:
алгоритм- это конечная совокупность точно заданных правил решения произвольного класса или набор инструкций, описывающих порядок действий исполнителя для решения некоторой . в старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.
ранее в языке писали «алгорифм», сейчас такое написание используется редко, но, тем не менее, имеет место исключение (нормальный алгорифм маркова).
часто в качестве исполнителя выступает компьютер, но понятие алгоритма необязательно относится к компьютерным программам, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек (а может быть и некоторый механизм, ткацкий станок, и
можно выделить алгоритмы вычислительные (о них в основном идет далее речь), и . вычислительные по сути преобразуют некоторые начальные данные в выходные, реализуя вычисление некоторой функции. семантика алгоритмов существенным образом может отличаться и сводиться к выдаче необходимых воздействий либо в заданные моменты времени, либо в качестве реакции на внешние события (в этом случае, в отличие от вычислительного алгоритма, может оставаться корректным при бесконечном выполнении).
понятие алгоритма относится к первоначальным, основным, базисным понятиям . вычислительные процессы алгоритмического характера (арифметические действия над целыми числами, нахождение наибольшего общего делителя двух чисел и т. д.) известны человечеству с глубокой древности. однако в явном виде понятие алгоритма сформировалось лишь в начале xx века.