C. Monster Invaders
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ziota нашел игру, которая назыается «Monster Invaders».

Аналогично другим RPG стрелялкам, в «Monster Invaders» требуется уничтожать монстров и боссов с помощью оружия.

Для простоты, мы рассмотрим только два вида монстров и три вида оружия.

А именно, два вида монстров это:

  • обычный монстр с $$$1$$$ hp.
  • босс с $$$2$$$ hp.

И три вида оружия:

  • Пистолет, наносит $$$1$$$ hp урона одному монстру, время перезарядки равно $$$r_1$$$
  • Лазерная пушка, наносит $$$1$$$ hp урона всем монстрам в данном уровне (включая босса), время перезарядки равно $$$r_2$$$
  • AWP, мгновенно убивает любого монстра, время перезарядки равно $$$r_3$$$

Исходно оружия незаряжены, и Ziota не может перезаряжать несколько оружий одновременно.

Этапы в игре могут быть описаны массивом $$$a_1, a_2, \ldots, a_n$$$, в котором $$$i$$$-й этап содержит $$$a_i$$$ обычных монстров и одного босса. Из-за натуры игры, Ziota не может использовать пистолет (оружие первого типа) или AWP (оружие третьего типа) чтобы выстрелить в босса, до того как будут убиты все $$$a_i$$$ обычных монстров.

Если Ziota ранит босса, но не убивает его полностью, он обязан уйти с текущего этапа на любой соседний этап (соседние к этапу $$$i$$$ $$$(1 < i < n)$$$ это этапы $$$i - 1$$$ и $$$i + 1$$$, единственный сосед этапа $$$1$$$ это этап $$$2$$$, единственный этап соседний к этапу $$$n$$$ это $$$n - 1$$$). Ziota также может уйти в любом соседний уровень в любой момент времени. Каждый переход между соседними уровнями выполняется с помощью портала, с временем телепортации $$$d$$$.

Чтобы не повредить пространственно-временной континуум внутри игры, запрещено перезаряжаться или стрелять в монстров во время телепортации.

Ziota начинает игру на этапе 1. Его задача довольно проста, убить всех монстров на всех этапах. Он хочет узнать минимальное время, которое ему нужно, чтобы этого добиться (вы можете считать, что выстрел в монстров происходит мгновенно и у него есть бесконечное количество патронов для каждого оружия). Пожалуйста, помогите ему найти это значение.

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

В первой строке записаны пять целых чисел, разделенных пробелами: $$$n$$$ $$$(2 \le n \le 10^6)$$$ — количество этапов, $$$r_1, r_2, r_3$$$ $$$(1 \le r_1 \le r_2 \le r_3 \le 10^9)$$$ — времена перезарядки трех оружий, $$$d$$$ $$$(1 \le d \le 10^9)$$$ — время перехода между соседними уровнями.

Во второй строке записаны $$$n$$$ разделенных пробелами целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^6, 1 \le i \le n)$$$.

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

Выведите одно целое число, минимальное время, которое требуется для прохождения игры.

Примеры
Входные данные
4 1 3 4 3
3 2 5 1
Выходные данные
34
Входные данные
4 2 4 4 1
4 5 1 2
Выходные данные
31
Примечание

В первом примере, оптимальная стратегия это:

  • Используйте пистолет чтобы убить трех обычных монстров и AWP, чтобы убить босса (Итоговое время равно $$$1\cdot3+4=7$$$)
  • Переместитесь на этап два (Итоговое время $$$7+3=10$$$)
  • Используйте пистолет дважды и AWP чтобы убить босса (Итоговое время $$$10+1\cdot2+4=16$$$)
  • Переместитесь на этап три (Итоговое время $$$16+3=19$$$)
  • Используйте лазерную пушку, теперь мы обязаны переместиться на этап два или четыре, мы движемся на этап четыре (Итоговое время $$$19+3+3=25$$$)
  • Используйте пистолет один раз, используйте AWP, чтобы убить босса (Итоговое время $$$25+1\cdot1+4=30$$$)
  • Двигайтесь обратно на этап три (Итоговое время $$$30+3=33$$$)
  • Убейте босса на третьем этапе пистолетом (Итоговое время $$$33+1=34$$$)

Обратите внимание, что здесь мы останавливаемся не на этапе $$$n$$$, а когда все боссы убиты.