You have a set of items, each having some integer weight not greater than 8. You denote that a subset of items is good if total weight of items in the subset does not exceed W.

You want to calculate the maximum possible weight of a good subset of items. Note that you have to consider the empty set and the original set when calculating the answer.

Input

The first line contains one integer W (0 ≤ W ≤ 10^{18}) — the maximum total weight of a good subset.

The second line denotes the set of items you have. It contains 8 integers cnt_1, cnt_2, ..., cnt_8 (0 ≤ cnt_i ≤ 10^{16}), where cnt_i is the number of items having weight i in the set.

Output

Print one integer — the maximum possible weight of a good subset of items.

Examples

Input


10
1 2 3 4 5 6 7 8


Output


10


Input


0
0 0 0 0 0 0 0 0


Output


0


Input


3
0 4 1 0 0 9 8 3


Output


3
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

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

    static class TaskE {
        boolean[][] visited;
        long[][] dp;

        long rec(int pos, int rem_weight, long[] cnt, int pack) {
            if (pos == 8) {
                return rem_weight == 0 ? 0 : -1;
            }

            if (visited[pos][rem_weight] == true) {
                return dp[pos][rem_weight];
            }
            visited[pos][rem_weight] = true;

            long res = -1;
            int used = 0;
            while (used <= cnt[pos] && used * (pos + 1) < pack && rem_weight - used * (pos + 1) >= 0) {
                long counter = ((cnt[pos] - used) * (pos + 1)) / pack;
                long cur_res = rec(pos + 1, rem_weight - used * (pos + 1), cnt, pack);
                if (cur_res != -1) {
                    assert (cur_res >= 0);
                    res = Math.max(res, cur_res + counter);
                }
                used++;
            }

            dp[pos][rem_weight] = res;
            return res;
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            long W = in.nextLong();
            long[] cnt = new long[8];
            for (int i = 0; i < 8; i++) {
                cnt[i] = in.nextLong();
            }
            int pack = 840;
            visited = new boolean[8][8 * pack + 1];
            dp = new long[8][8 * pack + 1];

            long ans = 0;
            for (int i = 0; i <= Math.min(8 * pack, W); i++) {
                long res = rec(0, i, cnt, pack);
                long bound = Math.min((W - i) / pack, res);
                ans = Math.max(ans, bound * pack + i);
            }
            out.println(ans);
            return;
        }

    }

    static class InputReader {
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputStream stream;

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

        private boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public long nextLong() {
            int c = read();
            while (isWhitespace(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isWhitespace(c));
            return res * sgn;
        }

    }
}

