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, …, 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 ≤ n ≤ 10^6) — the number of stages, r_1, r_2, r_3 (1 ≤ r_1 ≤ r_2 ≤ r_3 ≤ 10^9) — the reload time of the three guns respectively, d (1 ≤ d ≤ 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, ..., a_n (1 ≤ a_i ≤ 10^6, 1 ≤ i ≤ 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⋅3+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⋅2+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⋅1+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.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using dd = double;
using pll = pair<ll, ll>;
using tll = tuple<ll, ll, ll>;
using qll = tuple<ll, ll, ll, ll>;
using vll = vector<ll>;
using vdd = vector<dd>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vqll = vector<qll>;
using vvll = vector<vll>;
using vvdd = vector<vdd>;
using vvpll = vector<vpll>;
using vvtll = vector<vtll>;
using vvqll = vector<vqll>;
using vvvll = vector<vvll>;
using vvvdd = vector<vvdd>;
using vvvpll = vector<vvpll>;
using vvvtll = vector<vvtll>;
using vvvqll = vector<vvqll>;
using vvvvll = vector<vvvll>;
using vvvvdd = vector<vvvdd>;
using vvvvpll = vector<vvvpll>;
using vvvvtll = vector<vvvtll>;
using vvvvqll = vector<vvvqll>;
constexpr ll INF = 1LL << 60;
constexpr dd EPS = 1e-11;
constexpr dd PI = 3.1415926535897932;
struct Fast {
  Fast() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(std::numeric_limits<double>::max_digits10);
  }
} fast;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline T MaxE(vector<T> &v, ll S, ll E) {
  T m = v[S];
  for (ll i = (S); i <= (E); i++) chmax(m, v[i]);
  return m;
}
template <class T>
inline T MinE(vector<T> &v, ll S, ll E) {
  T m = v[S];
  for (ll i = (S); i <= (E); i++) chmin(m, v[i]);
  return m;
}
template <class T>
inline T MaxE(vector<T> &v, ll N) {
  return MaxE(v, 0, N - 1);
}
template <class T>
inline T MinE(vector<T> &v, ll N) {
  return MinE(v, 0, N - 1);
}
template <class T>
inline T MaxE(vector<T> &v) {
  return MaxE(v, (ll)v.size());
}
template <class T>
inline T MinE(vector<T> &v) {
  return MinE(v, (ll)v.size());
}
template <class T>
inline ll MaxI(vector<T> &v, ll S, ll E) {
  ll m = S;
  for (ll i = (S); i <= (E); i++) {
    if (v[i] > v[m]) m = i;
  }
  return m;
}
template <class T>
inline ll MinI(vector<T> &v, ll S, ll E) {
  ll m = S;
  for (ll i = (S); i <= (E); i++) {
    if (v[i] < v[m]) m = i;
  }
  return m;
}
template <class T>
inline ll MaxI(vector<T> &v, ll N) {
  return MaxI(v, 0, N - 1);
}
template <class T>
inline ll MinI(vector<T> &v, ll N) {
  return MinI(v, 0, N - 1);
}
template <class T>
inline ll MaxI(vector<T> &v) {
  return MaxI(v, (ll)v.size());
}
template <class T>
inline ll MinI(vector<T> &v) {
  return MinI(v, (ll)v.size());
}
template <class T>
inline T Sum(vector<T> &v, ll S, ll E) {
  T s = T();
  for (ll i = (S); i <= (E); i++) s += v[i];
  return s;
}
template <class T>
inline T Sum(vector<T> &v) {
  return Sum(v, 0, v.size() - 1);
}
template <class T>
inline ll sz(T &v) {
  return (ll)v.size();
}
template <class T>
inline T POW(T a, ll n) {
  T r = 1;
  for (; n > 0; n >>= 1, a *= a) {
    if (n & 1) r *= a;
  }
  return r;
}
inline ll POW(int a, ll n) { return POW((ll)a, n); }
inline ll CEIL(ll a, ll b) { return (a + b - 1) / b; }
ll Gcd(ll a, ll b) { return (b == 0) ? a : Gcd(b, a % b); }
ll Lcm(ll a, ll b) { return a * b / Gcd(a, b); }
inline ll MSB(ll a) {
  for (ll o = 63, x = -1;;) {
    ll m = (o + x) / 2;
    if (a < (1LL << m))
      o = m;
    else
      x = m;
    if (o - x == 1) return x;
  }
}
inline ll Upper2N(ll s) { return 1LL << MSB(s) << 1; }
inline vll Bit2Idx(ll m) {
  vll v;
  for (ll i = 0; m; m >>= 1, i++)
    if (m & 1) v.push_back(i);
  return v;
}
inline ll BitNum(ll m) {
  for (ll c = 0;; m >>= 1) {
    c += m & 1;
    if (!m) return c;
  }
}
inline ll Bit(ll s, ll i) { return (s >> i) & 1; }
[[nodiscard]] inline ll BitOn(ll s, ll i) { return s | (1LL << i); }
[[nodiscard]] inline ll BitOff(ll s, ll i) { return s & ~(1LL << i); }
[[nodiscard]] inline ll BitCut(ll s, ll i) { return s & ((1LL << ++i) - 1); }
inline vll str2num(string &s, ll N) {
  vll v(N);
  for (ll i = (0); i <= ((N)-1); i++) v[i] = (ll)(s[i] - '0');
  return v;
}
inline vll ALP2num(string &s, ll N) {
  vll v(N);
  for (ll i = (0); i <= ((N)-1); i++) v[i] = (ll)(s[i] - 'A');
  return v;
}
inline vll alp2num(string &s, ll N) {
  vll v(N);
  for (ll i = (0); i <= ((N)-1); i++) v[i] = (ll)(s[i] - 'a');
  return v;
}
template <class T>
inline ll FloorIdx(vector<T> &v, T x) {
  return upper_bound((v).begin(), (v).end(), x) - v.begin() - 1;
}
template <class T>
inline ll CeilIdx(vector<T> &v, T x) {
  return lower_bound((v).begin(), (v).end(), x) - v.begin();
}
template <class T>
inline ll UnderNumOf(vector<T> &v, T x) {
  return upper_bound(v.begin(), v.end(), x) - v.begin();
}
template <class T, class Pr>
inline ll UnderNumOf(vector<T> &v, T x, Pr pred) {
  return upper_bound(v.begin(), v.end(), x, pred) - v.begin();
}
template <class T>
inline ll OverNumOf(vector<T> &v, T x) {
  return (ll)v.size() - (lower_bound(v.begin(), v.end(), x) - v.begin());
}
template <class T, class Pr>
inline ll OverNumOf(vector<T> &v, T x, Pr pred) {
  return (ll)v.size() - (lower_bound(v.begin(), v.end(), x, pred) - v.begin());
}
template <class T = ll>
inline vector<T> cinv(ll N) {
  vector<T> v(N);
  for (ll i = (0); i <= ((N)-1); i++) cin >> v[i];
  return v;
}
template <class T, class S>
inline vector<pair<T, S>> cinv2(ll N) {
  vector<pair<T, S>> v(N);
  for (ll i = (0); i <= ((N)-1); i++) {
    cin >> v[i].first >> v[i].second;
  }
  return v;
}
template <class T>
inline vector<T> cinv2(ll N) {
  vector<T> v(N);
  for (ll i = (0); i <= ((N)-1); i++) {
    ll a, b;
    cin >> a >> b;
    v[i] = {a, b};
  }
  return v;
}
template <class T, class S, class R>
inline vector<tuple<T, S, R>> cinv3(ll N) {
  vector<tuple<T, S, R>> v(N);
  for (ll i = (0); i <= ((N)-1); i++) {
    cin >> get<0>(v[i]) >> get<1>(v[i]) >> get<2>(v[i]);
  }
  return v;
}
template <class T>
inline vector<T> cinv3(ll N) {
  vector<T> v(N);
  for (ll i = (0); i <= ((N)-1); i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    v[i] = {a, b, c};
  }
  return v;
}
template <class T, class S, class R, class Q>
inline vector<tuple<T, S, R, Q>> cinv4(ll N) {
  vector<tuple<T, S, R, Q>> v(N);
  for (ll i = (0); i <= ((N)-1); i++) {
    cin >> get<0>(v[i]) >> get<1>(v[i]) >> get<2>(v[i]) >> get<3>(v[i]);
  }
  return v;
}
template <class T>
inline vector<T> cinv4(ll N) {
  vector<T> v(N);
  for (ll i = (0); i <= ((N)-1); i++) {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    v[i] = {a, b, c, d};
  }
  return v;
}
template <class T = ll>
inline vector<vector<T>> cinvv(ll N, ll M) {
  vector<vector<T>> vv(N);
  for (ll i = (0); i <= ((N)-1); i++) vv[i] = cinv(M);
  return vv;
}
template <class T>
inline void coutv(vector<T> &v, string d = " ") {
  ll N = (ll)v.size();
  for (ll i = (0); i <= ((N)-1); i++) {
    cout << v[i] << ((i == N - 1) ? "" : d);
  }
  cout << '\n';
}
template <class T>
inline void coutv(deque<T> &v, string d = " ") {
  ll N = (ll)v.size();
  for (ll i = (0); i <= ((N)-1); i++) {
    cout << v[i] << ((i == N - 1) ? "" : d);
  }
  cout << '\n';
}
template <class T>
void bye(T a) {
  cout << a << '\n';
  exit(0);
}
template <class T>
void dump(vector<T> &v) {}
template <class T>
void dump(vector<vector<T>> &v) {}
template <class T>
void dump(vector<vector<vector<T>>> &v) {}
template <class T>
void dump(vector<vector<vector<vector<T>>>> &v) {}
template <class T>
void dump(vector<vector<vector<vector<vector<T>>>>> &v) {}
template <ll MOD>
struct mll_ {
  ll val;
  mll_(ll v = 0) : val(v % MOD) {
    if (val < 0) val += MOD;
  }
  mll_ operator-() const { return -val; }
  mll_ operator+(const mll_ &b) const { return val + b.val; }
  mll_ operator-(const mll_ &b) const { return val - b.val; }
  mll_ operator*(const mll_ &b) const { return val * b.val; }
  mll_ operator/(const mll_ &b) const { return mll_(*this) /= b; }
  mll_ operator+(ll b) const { return *this + mll_(b); }
  mll_ operator-(ll b) const { return *this - mll_(b); }
  mll_ operator*(ll b) const { return *this * mll_(b); }
  friend mll_ operator+(ll a, const mll_ &b) { return b + a; }
  friend mll_ operator-(ll a, const mll_ &b) { return -b + a; }
  friend mll_ operator*(ll a, const mll_ &b) { return b * a; }
  friend mll_ operator/(ll a, const mll_ &b) { return mll_(a) / b; }
  mll_ &operator+=(const mll_ &b) {
    val = (val + b.val) % MOD;
    return *this;
  }
  mll_ &operator-=(const mll_ &b) {
    val = (val + MOD - b.val) % MOD;
    return *this;
  }
  mll_ &operator*=(const mll_ &b) {
    val = (val * b.val) % MOD;
    return *this;
  }
  mll_ &operator/=(const mll_ &b) {
    ll c = b.val, d = MOD, u = 1, v = 0;
    while (d) {
      ll t = c / d;
      c -= t * d;
      swap(c, d);
      u -= t * v;
      swap(u, v);
    }
    val = val * u % MOD;
    if (val < 0) val += MOD;
    return *this;
  }
  mll_ &operator+=(ll b) { return *this += mll_(b); }
  mll_ &operator-=(ll b) { return *this -= mll_(b); }
  mll_ &operator*=(ll b) { return *this *= mll_(b); }
  mll_ &operator/=(ll b) { return *this /= mll_(b); }
  bool operator==(const mll_ &b) { return val == b.val; }
  bool operator!=(const mll_ &b) { return val != b.val; }
  bool operator==(ll b) { return *this == mll_(b); }
  bool operator!=(ll b) { return *this != mll_(b); }
  friend bool operator==(ll a, const mll_ &b) { return mll_(a) == b.val; }
  friend bool operator!=(ll a, const mll_ &b) { return mll_(a) != b.val; }
  friend ostream &operator<<(ostream &os, const mll_ &a) { return os << a.val; }
  friend istream &operator>>(istream &is, mll_ &a) { return is >> a.val; }
  static mll_ Combination(ll a, ll b) {
    chmin(b, a - b);
    if (b < 0) return mll_(0);
    mll_ c = 1;
    for (ll i = (0); i <= ((b)-1); i++) c *= a - i;
    for (ll i = (0); i <= ((b)-1); i++) c /= i + 1;
    return c;
  }
};
using mll = mll_<1000000007LL>;
using vmll = std::vector<mll>;
using vvmll = std::vector<vmll>;
using vvvmll = std::vector<vvmll>;
using vvvvmll = std::vector<vvvmll>;
using vvvvvmll = std::vector<vvvvmll>;
template <class T, class S>
inline pair<T, S> &operator+=(pair<T, S> &a, const pair<T, S> &b) {
  a.first += b.first;
  a.second += b.second;
  return a;
}
template <class T, class S>
inline pair<T, S> &operator-=(pair<T, S> &a, const pair<T, S> &b) {
  a.first -= b.first;
  a.second -= b.second;
  return a;
}
template <class T, class S>
inline pair<T, S> &operator*=(pair<T, S> &a, const pair<T, S> &b) {
  a.first *= b.first;
  a.second *= b.second;
  return a;
}
template <class T, class S>
inline pair<T, S> &operator/=(pair<T, S> &a, const pair<T, S> &b) {
  a.first /= b.first;
  a.second /= b.second;
  return a;
}
template <class T, class S>
inline pair<T, S> &operator%=(pair<T, S> &a, const pair<T, S> &b) {
  a.first %= b.first;
  a.second %= b.second;
  return a;
}
template <class T, class S, class R>
inline pair<T, S> &operator+=(pair<T, S> &a, R b) {
  a.first += b;
  a.second += b;
  return a;
}
template <class T, class S, class R>
inline pair<T, S> &operator-=(pair<T, S> &a, R b) {
  a.first -= b;
  a.second -= b;
  return a;
}
template <class T, class S, class R>
inline pair<T, S> &operator*=(pair<T, S> &a, R b) {
  a.first *= b;
  a.second *= b;
  return a;
}
template <class T, class S, class R>
inline pair<T, S> &operator/=(pair<T, S> &a, R b) {
  a.first /= b;
  a.second /= b;
  return a;
}
template <class T, class S, class R>
inline pair<T, S> &operator%=(pair<T, S> &a, R b) {
  a.first %= b;
  a.second %= b;
  return a;
}
template <class T, class S>
inline ostream &operator<<(ostream &os, const pair<T, S> &a) {
  return os << a.first << ' ' << a.second;
}
template <class T>
inline vector<T> &operator+=(vector<T> &a, const vector<T> &b) {
  for (ll i = 0; i < (ll)a.size(); i++) a[i] += b[i];
  return a;
}
template <class T>
inline vector<T> &operator-=(vector<T> &a, const vector<T> &b) {
  for (ll i = 0; i < (ll)a.size(); i++) a[i] -= b[i];
  return a;
}
template <class T>
inline vector<T> &operator*=(vector<T> &a, const vector<T> &b) {
  for (ll i = 0; i < (ll)a.size(); i++) a[i] *= b[i];
  return a;
}
template <class T>
inline vector<T> &operator/=(vector<T> &a, const vector<T> &b) {
  for (ll i = 0; i < (ll)a.size(); i++) a[i] /= b[i];
  return a;
}
template <class T>
inline vector<T> &operator%=(vector<T> &a, const vector<T> &b) {
  for (ll i = 0; i < (ll)a.size(); i++) a[i] %= b[i];
  return a;
}
template <class T, class S>
inline vector<T> &operator+=(vector<T> &a, S b) {
  for (T &e : a) e += b;
  return a;
}
template <class T, class S>
inline vector<T> &operator-=(vector<T> &a, S b) {
  for (T &e : a) e -= b;
  return a;
}
template <class T, class S>
inline vector<T> &operator*=(vector<T> &a, S b) {
  for (T &e : a) e *= b;
  return a;
}
template <class T, class S>
inline vector<T> &operator/=(vector<T> &a, S b) {
  for (T &e : a) e /= b;
  return a;
}
template <class T, class S>
inline vector<T> &operator%=(vector<T> &a, S b) {
  for (T &e : a) e %= b;
  return a;
}
template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &a) {
  for (ll i = 0; i < (ll)a.size(); i++) {
    if (i > 0) os << ' ';
    os << a[i];
  }
  return os;
}
template <class T>
struct CumulativeSumG {
  ll s = 0, e = -1;
  vector<T> cum;
  CumulativeSumG(){};
  CumulativeSumG(vector<T> &v) : e(v.size() - 1), cum(e + 2) { Ini(v); }
  CumulativeSumG(vector<T> &v, ll S, ll E) : s(S), e(E), cum(e - s + 2) {
    Ini(v);
  }
  void init(vector<T> &v) {
    e = v.size() - 1;
    cum.resize(e + 2);
    Ini(v);
  }
  void init(vector<T> &v, ll S, ll E) {
    s = S;
    e = E;
    cum.resize(e - s + 2);
    Ini(v);
  }
  void add(T x) {
    e++;
    cum.push_back(cum.back() + x);
  }
  T operator()(ll begin, ll end) { return cum[end + 1 - s] - cum[begin - s]; }
  void Ini(vector<T> &v) {
    for (ll i = (s); i <= (e); i++) cum[i + 1 - s] = cum[i - s] + v[i];
  }
};
using CumulativeSum = CumulativeSumG<ll>;
void solve() {
  ll n;
  cin >> n;
  ll r1, r2, r3;
  cin >> r1 >> r2 >> r3;
  ll d;
  cin >> d;
  vector<ll> a = cinv<ll>(n);
  vll X(n);
  for (ll i = (0); i <= (n - 1); i++) {
    X[i] = r1 * (a[i] + 2);
    chmin(X[i], r2 + r1);
  }
  vll Y(n);
  for (ll i = (0); i <= (n - 1); i++) {
    Y[i] = r1 * a[i] + r3;
  }
  CumulativeSum cum(X);
  vll dp_(n + 2, INF);
  auto dp = [&](ll i) -> ll & { return dp_[i + 2]; };
  dp(-1) = -d;
  for (ll i = (0); i <= (n - 1); i++) {
    chmin(dp(i), dp(i - 1) + Y[i] + d);
    if (i >= 1) {
      chmin(dp(i), dp(i - 2) + X[i - 1] + X[i] + 4 * d);
    }
  }
  ll ans = dp(n - 1);
  for (ll i = (-1); i <= (n - 3); i++) {
    ll p = n - i - 2;
    ll v;
    v = dp(i) + cum(i + 1, n - 1) + (2 * p + 3) * d;
    chmin(ans, v);
    v = dp(i) + cum(i + 1, n - 2) + Y[n - 1] + (2 * p + 1) * d;
    chmin(ans, v);
  }
  cout << ans << '\n';
}
int main() {
  solve();
  return 0;
}
