Ziota found a video game called "Monster Invaders".

Similar to every other shooting RPG game, "Monster Invaders" involves killing monsters and bosses with guns.

For the sake of simplicity, we only consider two different types of monsters and three different types of guns.

Namely, the two types of monsters are:   a normal monster with $1$ hp.  a boss with $2$ hp. 

And the three types of guns are:   Pistol, deals $1$ hp in damage to one monster, $r_1$ reloading time  Laser gun, deals $1$ hp in damage to all the monsters in the current level (including the boss), $r_2$ reloading time  AWP, instantly kills any monster, $r_3$ reloading time 

The guns are initially not loaded, and the Ziota can only reload 1 gun at a time.

The levels of the game can be considered as an array $a_1, a_2, \ldots, a_n$, in which the $i$-th stage has $a_i$ normal monsters and 1 boss. Due to the nature of the game, Ziota cannot use the Pistol (the first type of gun) or AWP (the third type of gun) to shoot the boss before killing all of the $a_i$ normal monsters.

If Ziota damages the boss but does not kill it immediately, he is forced to move out of the current level to an arbitrary adjacent level (adjacent levels of level $i$ $(1 < i < n)$ are levels $i - 1$ and $i + 1$, the only adjacent level of level $1$ is level $2$, the only adjacent level of level $n$ is level $n - 1$). Ziota can also choose to move to an adjacent level at any time. Each move between adjacent levels are managed by portals with $d$ teleportation time.

In order not to disrupt the space-time continuum within the game, it is strictly forbidden to reload or shoot monsters during teleportation. 

Ziota starts the game at level 1. The objective of the game is rather simple, to kill all the bosses in all the levels. He is curious about the minimum time to finish the game (assuming it takes no time to shoot the monsters with a loaded gun and Ziota has infinite ammo on all the three guns). Please help him find this value.


-----Input-----

The first line of the input contains five integers separated by single spaces: $n$ $(2 \le n \le 10^6)$ — the number of stages, $r_1, r_2, r_3$ $(1 \le r_1 \le r_2 \le r_3 \le 10^9)$ — the reload time of the three guns respectively, $d$ $(1 \le d \le 10^9)$ — the time of moving between adjacent levels.

The second line of the input contains $n$ integers separated by single spaces $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^6, 1 \le i \le n)$.


-----Output-----

Print one integer, the minimum time to finish the game.


-----Examples-----
Input
4 1 3 4 3
3 2 5 1

Output
34
Input
4 2 4 4 1
4 5 1 2

Output
31


-----Note-----

In the first test case, the optimal strategy is:  Use the pistol to kill three normal monsters and AWP to kill the boss (Total time $1\cdot3+4=7$)  Move to stage two (Total time $7+3=10$)  Use the pistol twice and AWP to kill the boss (Total time $10+1\cdot2+4=16$)  Move to stage three (Total time $16+3=19$)  Use the laser gun and forced to move to either stage four or two, here we move to stage four (Total time $19+3+3=25$)  Use the pistol once, use AWP to kill the boss (Total time $25+1\cdot1+4=30$)  Move back to stage three (Total time $30+3=33$)  Kill the boss at stage three with the pistol (Total time $33+1=34$) 

Note that here, we do not finish at level $n$, but when all the bosses are killed.

Difficulty: HARD

Starter code:

Solutions:
import sys
input = sys.stdin.readline
(N, a, b, c, k) = map(int, input().split())
X = list(map(int, input().split()))
costs = [0, 10 ** 18]
R = 10 ** 18
for i in range(N):
	if i == N - 2:
		R = min(costs) + X[-1] * a + c + min(a * (X[-2] + 2), a + b) + k
	costs = [min(costs[0] + a * X[i] + c, costs[1] + min(a * (X[i] + 2), a + b)), costs[0] + min(a * (X[i] + 2), a + b) + 2 * k]
R = min(R, min(costs))
print(R + k * (N - 1))


import sys
input = sys.stdin.readline
(N, a, b, c, k) = map(int, input().split())
X = list(map(int, input().split()))
(x, y) = (0, 10 ** 18)
R = 10 ** 18
for i in range(N):
	mnc = min(a * (X[i] + 2), a + b)
	if i != N - 1:
		(x, y) = (min(x + a * X[i] + c, y + mnc, x + mnc + 2 * k), x + mnc + 2 * k)
	else:
		(x, y) = (min(x + a * X[i] + c, y + mnc, x + mnc + 2 * k, y + a * X[i] + c - k), x + mnc + 2 * k)
print(min(R, x) + k * (N - 1))


(n, r1, r2, r3, D) = map(int, input().split())
state = [0, 0]
a = list(map(int, input().split()))
state[0] = r1 * a[0] + r3
state[1] = min(r2 + r1 + D, r1 * (a[0] + 2) + D)
for i in range(1, n - 1):
	newState = [-1, -1]
	newState[0] = min(state[1] + D + r1 * a[i] + r3, state[0] + r1 * a[i] + r3, state[1] + r2 + r1 + D, state[1] + r1 * (a[i] + 2) + D)
	newState[1] = min(state[0] + r2 + r1 + D, state[0] + r1 * (a[i] + 2) + D)
	state = newState
ans = min(state[0] + r1 * a[-1] + r3, state[0] + 2 * D + r2 + r1, state[0] + 2 * D + r1 * (a[-1] + 2), state[1] + r1 * a[-1] + r3, state[1] + r2 + r1 + D, state[1] + r1 * (a[-1] + 2) + D)
print(ans + D * (n - 1))


mod = 1000000007
eps = 10 ** (-9)
inf = 10 ** 18

def main():
	import sys
	input = sys.stdin.readline
	(N, r1, r2, r3, d) = map(int, input().split())
	A = list(map(int, input().split()))
	dp = [inf] * (N + 1)
	dp[0] = -d
	for i in range(N):
		a = A[i]
		dp[i + 1] = min(dp[i + 1], dp[i] + d + a * r1 + r3)
		if i + 1 == N:
			dp[i + 1] = min(dp[i + 1], dp[i] + d * 3 + min(r2 + r1, r1 * (a + 2)))
		if i + 1 < N:
			if i + 2 != N:
				dp[i + 2] = min(dp[i + 2], dp[i] + d * 4 + min(r2 + r1, r1 * (a + 2)) + min(r2 + r1, r1 * (A[i + 1] + 2), r1 * A[i + 1] + r3))
			else:
				dp[i + 2] = min(dp[i + 2], dp[i] + d * 4 + min(r2 + r1, r1 * (a + 2)) + min(r2 + r1, r1 * (A[i + 1] + 2)), dp[i] + d * 3 + min(r2 + r1, r1 * (a + 2)) + r1 * A[i + 1] + r3)
	print(dp[N])
main()


from sys import stdin, stdout

def monster_invaders(n, r1, r2, r3, d, a_a):
	dp = [[10 ** 18, 10 ** 18] for _ in range(n)]
	dp[0][0] = r1 * a_a[0] + r3
	dp[0][1] = min(r2, r1 * (a_a[0] + 1))
	for i in range(1, n):
		dp[i][0] = min(dp[i][0], dp[i - 1][0] + d + r1 * a_a[i] + r3)
		dp[i][0] = min(dp[i][0], dp[i - 1][1] + d + (r1 * a_a[i] + r3) + d + r1 + d)
		dp[i][0] = min(dp[i][0], dp[i - 1][1] + d + min(r2, r1 * (a_a[i] + 1)) + d + r1 + d + r1)
		dp[i][1] = min(dp[i][1], dp[i - 1][0] + d + min(r2, r1 * (a_a[i] + 1)))
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + d + d + r1 + d + min(r2, r1 * (a_a[i] + 1)))
		if i == n - 1:
			dp[i][0] = min(dp[i][0], dp[i - 1][1] + d + (r1 * a_a[i] + r3) + d + r1)
	return dp[n - 1][0]

def monster_invaders2(n, r1, r2, r3, d, a_a):
	dp = [[10 ** 18, 10 ** 18] for _ in range(2)]
	dp[0][0] = r1 * a_a[0] + r3
	dp[0][1] = min(r2, r1 * (a_a[0] + 1))
	i = 1
	for j in range(1, n):
		dp[i][0] = min(dp[i][0], dp[i - 1][0] + d + r1 * a_a[j] + r3)
		dp[i][0] = min(dp[i][0], dp[i - 1][1] + d + (r1 * a_a[j] + r3) + d + r1 + d)
		dp[i][0] = min(dp[i][0], dp[i - 1][1] + d + min(r2, r1 * (a_a[j] + 1)) + d + r1 + d + r1)
		dp[i][1] = min(dp[i][1], dp[i - 1][0] + d + min(r2, r1 * (a_a[j] + 1)))
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + d + d + r1 + d + min(r2, r1 * (a_a[j] + 1)))
		if j == n - 1:
			dp[i][0] = min(dp[i][0], dp[i - 1][1] + d + (r1 * a_a[j] + r3) + d + r1)
		dp[0] = dp[1]
		dp[1] = [10 ** 18, 10 ** 18]
	return dp[0][0]
(n, r1, r2, r3, d) = map(int, stdin.readline().split())
a_a = list(map(int, stdin.readline().split()))
ans = monster_invaders2(n, r1, r2, r3, d, a_a)
stdout.write(str(ans) + '\n')


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write('\n'.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
mod = int(1000000000.0) + 7
INF = 2 ** 32
(n, r1, r2, r3, d) = mdata()
a = mdata()
(dp1, dp2, dp3) = ([0] * n, [0] * n, [0] * n)
dp1[0] = min(r1, r3) * a[0] + r3
dp2[0] = min((a[0] + 1) * r1, r2) + d + min(r1, r2, r3)
dp3[0] = min((a[0] + 1) * r1, r2) + 2 * d + min(r1, r2, r3)
for i in range(1, n):
	dp1[i] = min(dp1[i - 1], dp2[i - 1] + d, dp3[i - 1]) + min(r1, r3) * a[i] + r3 + d
	dp3[i] = dp2[i - 1] + min((a[i] + 1) * r1, r2) + 2 * d + min(r1, r2, r3)
	dp2[i] = min(dp1[i - 1], dp3[i - 1]) + 2 * d + min((a[i] + 1) * r1, r2) + min(r1, r2, r3)
dp1[-1] = min(dp1[-2], dp2[-2], dp3[-2]) + min(r1, r3) * a[i] + r3 + d
out(min(dp1[-1], dp2[-1] + d, dp3[-1]))


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
(n, r1, r2, r3, d) = map(int, input().split())
a = list(map(int, input().split()))
dp = [0, float('inf')]
for i in range(1, n + 1):
	na = a[i - 1]
	ndp = [float('inf'), float('inf')]
	c1 = r1 * na + r3
	c2 = min(r1 * (na + 2), r2 + r1)
	if i != n:
		ndp[0] = min(dp[0] + c1, dp[1] + min(c1, c2))
		ndp[1] = dp[0] + c2 + 2 * d
	if i == n:
		print(min(dp[0] + c1, dp[0] + c2 + 2 * d, dp[1] + c2, dp[1] + c1 - d) + d * (n - 1))
	dp = ndp


(N, R1, R2, R3, D) = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0, 0] for _ in A]
dp[0][0] = R1 * A[0] + R3
dp[0][1] = min(R2, R1 * A[0] + R1)
for (i, a) in enumerate(A[1:-1], 1):
	dp[i][0] = min(dp[i - 1][0] + D + R1 * A[i] + R3, dp[i - 1][1] + D + min(R1 * A[i] + R3 + 2 * D + R1, R2 + 2 * D + 2 * R1, R1 * A[i] + 2 * R1 + 2 * D + R1))
	dp[i][1] = min(dp[i - 1][0] + D + min(R1 * A[i] + R1, R2), dp[i - 1][1] + D + min(R1 * A[i] + 2 * D + 2 * R1, R2 + 2 * D + R1))
dp[-1][0] = min(dp[-2][0] + D + min(R1 * A[-1] + R3, R2 + 2 * D + R1, R1 * A[-1] + 2 * R1 + 2 * D), dp[-2][1] + D + min(R1 * A[-1] + R3 + D + R1, R2 + 2 * D + 2 * R1, R1 * A[-1] + R1 + 2 * D + 2 * R1))
print(dp[-1][0])


(n, r1, r2, r3, d) = map(int, input().split())
a = list(map(int, input().split()))
if 2 * r1 < r3:
	save = [r3 - 2 * r1] * n
else:
	save = [0] * n
for i in range(n):
	save[i] = max(save[i], a[i] * r1 + r3 - r2 - r1)
ans = (n - 1) * d + sum(a) * r1 + n * r3
dp = [0, 0]
for i in range(n):
	dp0 = dp[1]
	dp1 = dp[1]
	if i + 1 < n and save[i] + save[i + 1] > 2 * d:
		dp1 = max(dp1, dp[0] + save[i] + save[i + 1] - 2 * d)
	if i == n - 1:
		dp1 = max(dp1, dp[0] + save[i] - 2 * d)
	if i == n - 2:
		dp0 = max(dp0, dp[0] + save[i] - d)
	dp1 = max(dp1, dp0)
	dp = [dp0, dp1]
print(ans - max(dp0, dp1))


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def chmin(i, j, val):
	if val < dp[i][j]:
		dp[i][j] = val
inf = 10 ** 16
(n, r1, r2, r3, d) = MI()
aa = LI()
dp = [[inf] * 2 for _ in range(n + 1)]
dp[0][0] = -d
for (i, a) in enumerate(aa):
	for j in range(2):
		pre = dp[i][j]
		if pre == inf:
			continue
		if j == 0:
			chmin(i + 1, 0, pre + d + r1 * a + r3)
			chmin(i + 1, 1, pre + d + min(r1 * (a + 1), r2))
		else:
			chmin(i + 1, 0, pre + d * 3 + min(r1 * (a + 1), r2) + r1 * 2)
print(min(dp[n][0], dp[n][1] + d * 2 + r1, dp[n - 1][1] + d * 2 + (aa[-1] + 1) * r1 + r3))


import pprint
(n, r1, r2, r3, d) = map(int, input().split())
(*arr,) = map(int, input().split())
dp = [[0] * (n + 1) for _ in range(2)]
dp[0][0] = -d
dp[1][0] = 2 * n * r2 + 2 * n * d
for i in range(n):
	fast_kill = arr[i] * r1 + r3
	slow_kill = min((arr[i] + 2) * r1, r2 + r1)
	extra = -d if i == n - 1 else 0
	dp[0][i + 1] = min(dp[0][i] + fast_kill, dp[1][i] + fast_kill + extra, dp[1][i] + slow_kill) + d
	dp[1][i + 1] = dp[0][i] + slow_kill + 3 * d
print(min(dp[0][-1], dp[1][-1]))


import sys
readline = sys.stdin.readline
INF = 10 ** 18
(N, r1, r2, r3, d) = map(int, readline().split())
A = list(map(int, readline().split()))
dp1 = [INF] * (N + 1)
dp2 = [INF] * (N + 1)
dp1[0] = -d
dp2 = -d
mj = INF
rr = r1 + r2
C = [0] * (N + 1)
for i in range(N):
	a = A[i]
	C[i + 1] = min(rr, (a + 2) * r1)
CC = C[:]
for i in range(1, N + 1):
	CC[i] += CC[i - 1]
for i in range(1, N + 1):
	a = A[i - 1]
	dp1[i] = dp2 + d + C[i]
	dp2 = min(dp2 + d + r1 * a + r3, CC[i] + 3 * d * i + mj)
	mj = min(mj, dp1[i] - 3 * i * d - CC[i])
ans = min(dp2, 2 * d + dp1[-1])
ans = min(ans, dp1[N - 1] + 3 * d + C[N])
zz = min(r1 * A[-1] + r3, 2 * d + min(rr, (A[-1] + 2) * r1))
for i in range(1, N):
	ans = min(ans, dp1[i] + 2 * (N - i) * d + zz + CC[N - 1] - CC[i])
print(ans)


import sys
input = sys.stdin.readline
(N, a, b, c, k) = map(int, input().split())
X = list(map(int, input().split()))
dp = [[10 ** 18] * 2 for _ in range(N + 1)]
dp[0][0] = 0
R = 10 ** 18
for i in range(N):
	dp[i + 1][0] = min(dp[i][0] + a * X[i] + c, dp[i][1] + min(a * (X[i] + 2), a + b))
	dp[i + 1][1] = dp[i][0] + min(a * (X[i] + 2), a + b) + 2 * k
R = min(dp[-3]) + X[-1] * a + c + min(a * (X[-2] + 2), a + b) + k
R = min(R, dp[-1][0])
R = min(R, dp[-1][1])
print(R + k * (N - 1))


import sys
input = sys.stdin.buffer.readline
(n, r1, r2, r3, d) = map(int, input().split())
a = list(map(int, input().split()))
dp = [1 << 60] * n
dp[0] = min(r1 * a[0] + r3, min(r1 * (a[0] + 1), r2) + r1 + 2 * d)
dp[1] = min(r1 * (a[0] + 1), r2) + d + min(r1 * (a[1] + 1), r2) + d + r1 + d + r1
for i in range(1, n):
	dp[i] = min(dp[i], dp[i - 1] + d + r1 * a[i] + r3)
	dp[i] = min(dp[i], dp[i - 1] + d + min(r1 * (a[i] + 1), r2) + 2 * d + r1)
	dp[i] = min(dp[i], dp[i - 2] + d + min(r1 * (a[i - 1] + 1), r2) + d + min(r1 * (a[i] + 1), r2) + d + r1 + d + r1)
res = dp[n - 1]
last = min(r1 * a[-1] + r3, min(r1 * (a[-1] + 1), r2) + r1 + 2 * d) + d
for i in range(n - 2, 0, -1):
	last += min(r1 * (a[i] + 2), r1 + r2) + 2 * d
	res = min(res, last + dp[i - 1])
print(res)


import sys
import math
input = sys.stdin.readline
(N, r1, r2, r3, d) = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
X = [None for i in range(N)]
Y = [None for i in range(N)]
X[0] = A[0] * r1 + r3
Y[0] = min(r2, A[0] * r1 + r1)
for i in range(1, N):
	x = A[i] * r1 + r3
	y = r2
	z = A[i] * r1 + r1
	X[i] = min(X[i - 1] + d + x, Y[i - 1] + d + x + d + r1 + (d if i != N - 1 else 0), Y[i - 1] + d + min(y, z) + d + r1 + d + r1)
	Y[i] = min(X[i - 1] + d + min(y, z), Y[i - 1] + d + min(y, z) + d + r1 + d)
print(X[N - 1])


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]
inf = 10 ** 16
(n, r1, r2, r3, d) = MI()
aa = LI()
dp0 = -d
dp1 = inf
pre1 = inf
for (i, a) in enumerate(aa):
	(pre0, pre1) = (dp0, dp1)
	dp0 = min(pre0 + d + r1 * a + r3, pre1 + d * 3 + min(r1 * (a + 1), r2) + r1 * 2)
	dp1 = pre0 + d + min(r1 * (a + 1), r2)
print(min(dp0, dp1 + d * 2 + r1, pre1 + d * 2 + (aa[-1] + 1) * r1 + r3))


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

def solve():
	(n, r1, r2, r3, d) = mints()
	s = min(r1, r3)
	r2s = r2 + s
	a = list(mints())
	dp = [1 << 63] * n
	dp[n - 1] = min(s * a[n - 1] + r3, d * 2 + min(r2s, s * (a[n - 1] + 2)))
	dp[n - 2] = min(s * a[n - 2] + r3 + d + dp[n - 1], min(r2s, s * (a[n - 1] + 2)) + min(r2s, s * (a[n - 2] + 2)) + d * 3)
	dp[n - 2] = min(dp[n - 2], min(r2s, s * (a[n - 2] + 2)) + d + s * a[n - 1] + r3 + d)
	for i in range(n - 3, -1, -1):
		dd = s * a[i] + r3 + d + dp[i + 1]
		x = min(s * a[i] + r3, min(r2s, s * (a[i] + 2))) + min(s * a[i + 1] + r3, min(r2s, s * (a[i + 1] + 2)))
		dp[i] = min(dd, x + dp[i + 2] + d * 4)
	print(dp[0])
solve()


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import sys
M = mod = 10 ** 9 + 7

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip().split()]

def st():
	return str(input().rstrip())[2:-1]

def val():
	return int(input().rstrip())

def li2():
	return [str(i)[2:-1] for i in input().rstrip().split()]

def li3():
	return [int(i) for i in st()]
(n, r1, r2, r3, d) = li()
l = li()
dp = [[0] * 2 for i in range(n + 1)]
dp[n][0] = -d
dp[n][1] = d + r1
for i in range(n - 1, -1, -1):
	temp = float('inf')
	temp = min(temp, (l[i] + 1) * r1 + d + dp[i + 1][1])
	temp = min(temp, r2 + d + dp[i + 1][1])
	temp = min(temp, l[i] * r1 + r3 + d + dp[i + 1][0])
	dp[i][0] = temp
	temp = float('inf')
	temp = min(temp, (l[i] + 3) * r1 + 3 * d + dp[i + 1][0])
	temp = min(temp, r2 + 2 * r1 + 3 * d + dp[i + 1][0])
	temp = min(temp, (l[i] + 1) * r1 + r3 + 3 * d + dp[i + 1][0])
	if i == n - 1:
		temp = min(temp, l[i] * r1 + r3 + d + r1)
	dp[i][1] = temp
print(dp[0][0])


import sys

def solve(lst, r1, r2, r3, d):
	console('----- solving ------')
	const_r2_r1_d = r2 + r1 + d
	const_2r1_d = 2 * r1 + d
	m1_cost = [r1 * x + r3 for x in lst]
	m4_cost = [min(r1 * x + const_2r1_d, const_r2_r1_d) for x in lst]
	baseline = sum(m1_cost) + (len(lst) - 1) * d
	cost_diff = [a - b for (a, b) in zip(m1_cost, m4_cost)]
	del m1_cost
	del m4_cost
	savings = [[0, 0] for _ in lst]
	savings[0][1] = max(cost_diff[0], -d)
	for i in range(1, len(lst)):
		savings[i][0] = max(savings[i - 1][0], savings[i - 1][1] + cost_diff[i], savings[i - 1][1] - d)
		savings[i][1] = max(savings[i - 1][0] + cost_diff[i], savings[i - 1][0] - d)
	total_savings = max(0, savings[-2][1], savings[-1][0], savings[-1][1] - d)
	return baseline - total_savings

def console(*args):
	return
inp = sys.stdin.readlines()
for _ in [1]:
	(_, r1, r2, r3, d) = list(map(int, inp[0].split()))
	lst = list(map(int, inp[1].split()))
	res = solve(lst, r1, r2, r3, d)
	print(res)


import io
import os
import sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def printd(*args, **kwargs):
	pass

def get_str():
	return input().decode().strip()

def rint():
	return map(int, input().split())

def oint():
	return int(input())
(n, r1, r2, r3, d) = rint()
a = list(rint())
printd(n, r1, r2, r3, d)
printd(a)
dp = [[10 ** 100, 10 ** 100] for i in range(n)]
dp[0][0] = r1 * a[0] + r3
dp[0][1] = min(r1 * a[0] + r1, r2)
for i in range(1, n):
	dp[i][0] = min(dp[i][0], dp[i - 1][0] + d + r1 * a[i] + r3)
	dp[i][0] = min(dp[i][0], dp[i - 1][1] + d + r1 * a[i] + r3 + d + r1 + d)
	dp[i][0] = min(dp[i][0], dp[i - 1][1] + d + r1 * a[i] + r1 + d + r1 + d + r1)
	dp[i][0] = min(dp[i][0], dp[i - 1][1] + d + r2 + d + r1 + d + r1)
	dp[i][1] = min(dp[i][1], dp[i - 1][0] + d + r1 * a[i] + r1)
	dp[i][1] = min(dp[i][1], dp[i - 1][0] + d + r2)
	dp[i][1] = min(dp[i][1], dp[i - 1][1] + d + r1 * a[i] + r1 + d + r1 + d)
	dp[i][1] = min(dp[i][1], dp[i - 1][1] + d + r2 + d + r1 + d)
	if i == n - 1:
		dp[i][0] = min(dp[i][0], dp[i - 1][1] + d + r1 * a[i] + r3 + d + r1)
printd(dp)
print(dp[n - 1][0])


from sys import stdin
(n, r1, r2, r3, d) = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
dp = [0, float('inf')]
for i in range(1, n + 1):
	na = a[i - 1]
	ndp = [float('inf'), float('inf')]
	c1 = r1 * na + r3
	c2 = min(r1 * (na + 2), r2 + r1)
	if i != n:
		ndp[0] = min(dp[0] + c1, dp[1] + min(c1, c2))
		ndp[1] = dp[0] + c2 + 2 * d
	if i == n:
		print(min(dp[0] + c1, dp[0] + c2 + 2 * d, dp[1] + c2, dp[1] + c1 - d) + d * (n - 1))
	dp = ndp


(N, a, b, c, k) = map(int, input().split())
X = list(map(int, input().split()))
(x, y) = (0, float('inf'))
for i in range(N):
	mnc = min(a * (X[i] + 2), a + b)
	if i != N - 1:
		(x, y) = (min(x + a * X[i] + c, y + mnc, x + mnc + 2 * k), x + mnc + 2 * k)
	else:
		(x, y) = (min(x + a * X[i] + c, y + mnc, x + mnc + 2 * k, y + a * X[i] + c - k), x + mnc + 2 * k)
print(x + k * (N - 1))


import sys
input = sys.stdin.readline
(n, r1, r2, r3, d) = map(int, input().split())
A = list(map(int, input().split()))
DP = [1 << 60] * n
DP2 = [1 << 60] * n
DP.append(0)
DP.append(0)
for i in range(n):
	DP[i] = min(DP[i], DP[i - 1] + r1 * A[i] + r3 + d)
	if i >= 1:
		DP2[i] = min(DP2[i], DP[i - 2] + min(r1 * (A[i - 1] + 1), r2) + min(r1 * (A[i] + 1), r2) + r1 * 2 + d * 4)
		DP2[i] = min(DP2[i], DP[i - 1] + min(r1 * (A[i] + 1), r2) + r1 + d * 3)
		DP[i] = min(DP[i], DP2[i])
ANS = DP[n - 1] - d
last = r1 * A[n - 1] + r3
for i in range(1, n):
	last += d * 2
	last += min(r1 * (A[n - 1 - i] + 1), r2) + r1
	ANS = min(ANS, DP[n - 2 - i] + last)
print(ANS)


import time

def calc_time_saved(i):
	global levels, pistol, awp, laser_time, pistol_time_saved
	return max(levels[i] * pistol + awp - laser_time, pistol_time_saved)
(n, pistol, laser, awp, tele) = map(int, input().split())
levels = list(map(int, input().split()))
total_time = sum(levels) * pistol + n * awp + (n - 1) * tele
laser_time = laser + pistol
pistol_time_saved = max(awp - 2 * pistol, 0)
smallest_time_save = calc_time_saved(0)
i = 0
time1 = 0
time2 = 0
while i < n - 2:
	a = max(levels[i] * pistol + awp - laser_time, pistol_time_saved)
	b = max(levels[i + 1] * pistol + awp - laser_time, pistol_time_saved)
	if a + b > 2 * tele:
		total_time += 2 * tele - a - b
		if b + smallest_time_save < 2 * tele:
			total_time += b + smallest_time_save - 2 * tele
			i += 1
			smallest_time_save = b
		else:
			i += 2
			smallest_time_save = min(a, smallest_time_save)
	else:
		i += 1
		if a > smallest_time_save:
			total_time += smallest_time_save - a
		smallest_time_save = b
if i == n - 2:
	a = calc_time_saved(i)
	b = calc_time_saved(i + 1)
	if a > tele:
		total_time += tele - a
		if b > tele:
			total_time += tele - b
	elif a + b > 2 * tele:
		total_time += 2 * tele - a - b
else:
	a = calc_time_saved(i)
	if min(a, smallest_time_save) > 2 * tele:
		total_time += 2 * tele - a
	elif max(a, tele) > smallest_time_save:
		total_time += smallest_time_save - max(a, tele)
print(total_time)


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(N, R1, R2, R3, D) = map(int, input().split())
A = list(map(int, input().split()))
A.reverse()
inf = 1 << 61
dp1 = [inf] * N
dp2 = [inf] * N
dp0 = [inf] * N
dpc = [inf] * N
a = A[0]
t1 = R1 * a + R3
t2 = min(R1 * a + R3 + D, R2 + R1 + D, R1 * (a + 2) + D)
dp0[0] = t1
dpc[0] = t1
dp1[0] = t2
ans1 = D * (N - 1)
ans3 = t2 + D * N
for (i, a) in enumerate(A[1:], 1):
	t1 = R1 * a + R3
	t2 = min(R1 * a + R3 + D, R2 + R1 + D, R1 * (a + 2) + D)
	dp0[i] = min(dp0[i - 1], dp2[i - 1], dpc[i - 1]) + t1
	dp1[i] = min(dp0[i - 1], dp2[i - 1]) + t2
	dp2[i] = dp1[i - 1] + t2
	dpc[i] = dpc[i - 1] + t2
	ans3 += t2
ans2 = min(dp0[N - 1], dp2[N - 1], dpc[N - 1])
ans = ans1 + ans2
ans = min(ans, ans3)
print(ans)


import sys
input = sys.stdin.buffer.readline
(n, r1, r2, r3, d) = map(int, input().split())
a = list(map(int, input().split()))
INF = 10 ** 18
vals = [val * r1 + r3 for val in a]
vals2 = [min(r2 + r1, (val + 2) * r1, vals[i]) for (i, val) in enumerate(a)]
dp = [INF] * (n + 1)
dp[0] = 0
for i in range(n):
	dp[i + 1] = vals[i] + d + dp[i]
	if i - 1 >= 0:
		dp[i + 1] = min(vals2[i] + vals2[i - 1] + 4 * d + dp[i - 1], dp[i + 1])
	if i - 2 >= 0:
		dp[i + 1] = min(vals2[i] + vals2[i - 1] + vals2[i - 2] + d * 7 + dp[i - 2], dp[i + 1])
ans = dp[-1] - d
last = min(vals[-1], vals2[-1] + 2 * d)
for i in range(n - 1)[::-1]:
	last += 2 * d + vals2[i]
	ans = min(dp[i] + last, ans)
print(ans)


from sys import stdin

class Input:

	def __init__(self):
		self.lines = stdin.read().splitlines()
		self.count = 0

	def readline(self):
		for line in self.lines:
			yield line

	def line(self):
		try:
			return self.lines[self.count]
		finally:
			self.count += 1

	def array(self, sep=' ', cast=int):
		return list(map(cast, self.line().split(sep=sep)))

	def known_tests(self):
		(num_of_cases,) = self.array()
		for case in range(num_of_cases):
			yield self

	def unknown_tests(self):
		while self.count < len(self.lines):
			yield self

class Problem:
	oo = float('inf')

	def __init__(self, input):
		(n, r1, r2, r3, d) = input.array()
		a = input.array()
		dp = [0, self.oo]
		for i in range(n):
			c0 = r1 * a[i] + r3
			c1 = min(r1 + r2, (a[i] + 2) * r1)
			if i + 1 == n:
				dp = [min(dp[0] + c0, dp[0] + c1 + 2 * d, dp[1] + c1, dp[1] + c0 - d), self.oo]
			else:
				dp = [min(dp[0] + c0, dp[1] + min(c0, c1)), dp[0] + c1 + 2 * d]
		print(d * (n - 1) + dp[0])
for tc in Input().unknown_tests():
	Problem(tc)


import sys
input = sys.stdin.readline

def snipe(i):
	global r1, r2, r3, arr
	return r1 * arr[i] + r3

def laser(i):
	global r1, r2, r3, arr
	return min(r1 * (arr[i] + 1), r2)
(n, r1, r2, r3, d) = list(map(int, input().split()))
arr = list(map(int, input().split()))
dp = [[sys.maxsize for j in range(2)] for i in range(n)]
dp[0][0] = snipe(0) + d
dp[0][1] = laser(0) + d
for i in range(1, n - 1):
	dp[i][0] = min(dp[i - 1][0] + snipe(i) + d, dp[i - 1][1] + laser(i) + 2 * r1 + 3 * d)
	dp[i][1] = dp[i - 1][0] + laser(i) + d
i = n - 1
ans = min(dp[i - 1][0] + snipe(i), dp[i - 1][1] + laser(i) + 2 * r1 + 2 * d, dp[i - 1][1] + snipe(i) + r1 + d, dp[i - 1][0] + laser(i) + 2 * d + r1)
print(ans)