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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.nio.ByteBuffer;
import java.util.OptionalLong;
import java.nio.charset.Charset;
import java.util.NoSuchElementException;
import java.io.OutputStream;
import java.util.stream.LongStream;
import java.nio.CharBuffer;
import java.io.IOException;
import java.nio.charset.CharsetDecoder;
import java.lang.reflect.Field;
import java.nio.charset.StandardCharsets;
import java.io.UncheckedIOException;
import java.security.AccessControlException;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper reloaded plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner2 in = new LightScanner2(inputStream);
        LightWriter2 out = new LightWriter2(outputStream);
        CMonsterInvaders solver = new CMonsterInvaders();
        solver.solve(1, in, out);
        out.close();
    }

    static class CMonsterInvaders {
        private static final long INF = (long) 2e18;

        public void solve(int testNumber, LightScanner2 in, LightWriter2 out) {
            int n = in.ints();
            long r1 = in.longs(), r2 = in.longs(), r3 = in.longs(), d = in.longs();
            long[] a = in.longs(n);
            //long x = a[n - 1];
            //long c1 = x * r1 + r3, c2 = IntMath.min(c1, (x + 2) * r1, r1 + r2);
            out.ans(calc(n, r1, r2, r3, d, a) + d * (n - 1L)).ln();
        }

        private static long calc(int n, long r1, long r2, long r3, long d, long[] a) {
            long[][] dp = new long[3][n + 1];
            ArrayUtil.fill(dp, INF);
            dp[0][0] = 0;
            for (int i = 0; i < n; i++) {
                long c1 = a[i] * r1 + r3;
                dp[0][i + 1] = Math.min(dp[0][i + 1], dp[0][i] + c1);
                dp[0][i + 1] = Math.min(dp[0][i + 1], dp[1][i] + c1); // free
                if (i != n - 1) {
                    dp[1][i + 1] = Math.min(dp[1][i + 1], dp[1][i] + c1 + 2 * d);
                    dp[1][i + 1] = Math.min(dp[1][i + 1], dp[0][i] + c1 + 2 * d);
                    dp[2][i + 1] = Math.min(dp[2][i + 1], dp[0][i] + c1 + d);
                    dp[2][i + 1] = Math.min(dp[2][i + 1], dp[1][i] + c1 + d);
                    dp[2][i + 1] = Math.min(dp[2][i + 1], dp[2][i] + c1 + d);
                } else {
                    // dp[2][i + 1] = Math.min(dp[2][i + 1], dp[0][i] + c1);
                    dp[2][i + 1] = Math.min(dp[2][i + 1], dp[2][i] + c1);
                }

                long c2 = Math.min((a[i] + 2L) * r1, r1 + r2);
                //dp[0][i + 1] = Math.min(dp[0][i + 1], dp[0][i]);
                dp[0][i + 1] = Math.min(dp[0][i + 1], dp[1][i] + c2); // free
                if (i != n - 1) {
                    dp[1][i + 1] = Math.min(dp[1][i + 1], dp[1][i] + c2 + 2 * d);
                    dp[1][i + 1] = Math.min(dp[1][i + 1], dp[0][i] + c2 + 2 * d);
                    dp[2][i + 1] = Math.min(dp[2][i + 1], dp[0][i] + c2 + d);
                    dp[2][i + 1] = Math.min(dp[2][i + 1], dp[1][i] + c2 + d);
                    dp[2][i + 1] = Math.min(dp[2][i + 1], dp[2][i] + c2 + d);
                } else {
                    dp[2][i + 1] = Math.min(dp[2][i + 1], dp[0][i] + c2 + 2 * d);
                    dp[2][i + 1] = Math.min(dp[2][i + 1], dp[2][i] + c2 + 2 * d);
                }
            }
            //System.out.println(Arrays.toString(dp[0]));
            //System.out.println(Arrays.toString(dp[1]));
            //System.out.println(Arrays.toString(dp[2]));
            return IntMath.min(dp[0][n], dp[1][n], dp[2][n]);
        }

    }

    static abstract class LightScannerAdapter implements AutoCloseable {
        public abstract String string();

        public long longs() {
            return Long.parseLong(string());
        }

        public final long[] longs(int length) {
            long[] res = new long[length];
            Arrays.setAll(res, ignored -> longs());
            return res;
        }

        public abstract void close();

    }

    static final class IntMath {
        private IntMath() {
        }

        public static long min(long... v) {
            return Arrays.stream(v).min().orElseThrow(NoSuchElementException::new);
        }

    }

    static class LightScanner2 extends LightScannerAdapter {
        private static final int BUF_SIZE = 32 * 1024;
        private final InputStream stream;
        private final StringBuilder builder = new StringBuilder();
        private final byte[] buf = new byte[BUF_SIZE];
        private int ptr;
        private int len;

        public LightScanner2(InputStream stream) {
            this.stream = stream;
        }

        private int read() {
            if (ptr < len) return buf[ptr++];
            try {
                ptr = 0;
                len = stream.read(buf);
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            if (len == -1) return -1;
            return buf[ptr++];
        }

        private void skip() {
            int b;
            while (isTokenSeparator(b = read()) && b != -1) ;
            if (b == -1) throw new NoSuchElementException("EOF");
            ptr--;
        }

        private void loadToken() {
            builder.setLength(0);
            skip();
            for (int b = read(); !isTokenSeparator(b); b = read()) {
                builder.appendCodePoint(b);
            }
        }

        public String string() {
            loadToken();
            return builder.toString();
        }

        public int ints() {
            long x = longs();
            if (x < Integer.MIN_VALUE || Integer.MAX_VALUE < x) throw new NumberFormatException("Overflow");
            return (int) x;
        }

        public long longs() {
            skip();
            int b = read();
            boolean negate;
            if (b == '-') {
                negate = true;
                b = read();
            } else negate = false;
            long x = 0;
            for (; !isTokenSeparator(b); b = read()) {
                if ('0' <= b && b <= '9') x = x * 10 + b - '0';
                else throw new NumberFormatException("Unexpected character '" + b + "'");
            }
            return negate ? -x : x;
        }

        public void close() {
            try {
                stream.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        private static boolean isTokenSeparator(int b) {
            return b < 33 || 126 < b;
        }

    }

    static final class ArrayUtil {
        private ArrayUtil() {
        }

        public static void fill(long[] a, long v) {
            Arrays.fill(a, v);
        }

        public static void fill(long[][] a, long v) {
            for (int i = 0; i < a.length; i++) {
                fill(a[i], v);
            }
        }

    }

    static class LightWriter2 implements AutoCloseable {
        private static final int BUF_SIZE = 32 * 1024;
        private static final int BUF_THRESHOLD = 1024;
        private final OutputStream out;
        private final byte[] buf = new byte[BUF_SIZE];
        private int ptr;
        private final Field fastStringAccess;
        private boolean autoflush = false;
        private boolean breaked = true;

        public LightWriter2(OutputStream out) {
            this.out = out;
            Field f;
            try {
                f = String.class.getDeclaredField("value");
                f.setAccessible(true);
                if (f.getType() != byte[].class) f = null;
            } catch (ReflectiveOperationException | AccessControlException ignored) {
                f = null;
            }
            this.fastStringAccess = f;
        }

        public LightWriter2(Writer out) {
            this.out = new LightWriter2.WriterOutputStream(out);
            this.fastStringAccess = null;
        }

        private void allocate(int n) {
            if (ptr + n <= BUF_SIZE) return;
            try {
                out.write(buf, 0, ptr);
                ptr = 0;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            if (BUF_SIZE < n) throw new IllegalArgumentException("Internal buffer exceeded");
        }

        public void close() {
            try {
                out.write(buf, 0, ptr);
                ptr = 0;
                out.flush();
                out.close();
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

        public LightWriter2 print(char c) {
            allocate(1);
            buf[ptr++] = (byte) c;
            breaked = false;
            return this;
        }

        public LightWriter2 print(String s) {
            byte[] bytes;
            if (this.fastStringAccess == null) bytes = s.getBytes();
            else {
                try {
                    bytes = (byte[]) fastStringAccess.get(s);
                } catch (IllegalAccessException ignored) {
                    bytes = s.getBytes();
                }
            }
            int n = bytes.length;
            if (n <= BUF_THRESHOLD) {
                allocate(n);
                System.arraycopy(bytes, 0, buf, ptr, n);
                ptr += n;
                return this;
            }
            try {
                out.write(buf, 0, ptr);
                ptr = 0;
                out.write(bytes);
                out.flush();
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            return this;
        }

        public LightWriter2 ans(long l) {
            if (!breaked) {
                print(' ');
            }
            breaked = false;
            if (l == 0) return print('0');
            if (l < 0) {
                print('-');
                l = -l;
            }
            int n = 0;
            long t = l;
            while (t > 0) {
                t /= 10;
                n++;
            }
            allocate(n);
            for (int i = 1; i <= n; i++) {
                buf[ptr + n - i] = (byte) (l % 10 + '0');
                l /= 10;
            }
            ptr += n;
            return this;
        }

        public LightWriter2 ln() {
            print(System.lineSeparator());
            breaked = true;
            if (autoflush) {
                try {
                    out.flush();
                } catch (IOException ex) {
                    throw new UncheckedIOException(ex);
                }
            }
            return this;
        }

        private static class WriterOutputStream extends OutputStream {
            final Writer writer;
            final CharsetDecoder decoder;

            WriterOutputStream(Writer writer) {
                this.writer = writer;
                this.decoder = StandardCharsets.UTF_8.newDecoder();
            }

            public void write(int b) throws IOException {
                writer.write(b);
            }

            public void write(byte[] b) throws IOException {
                writer.write(decoder.decode(ByteBuffer.wrap(b)).array());
            }

            public void write(byte[] b, int off, int len) throws IOException {
                writer.write(decoder.decode(ByteBuffer.wrap(b, off, len)).array());
            }

            public void flush() throws IOException {
                writer.flush();
            }

            public void close() throws IOException {
                writer.close();
            }

        }

    }
}

