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.BufferedOutputStream;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Task {

    public static void solve() throws Exception {
	long maxSum = nextLong();
	long[] arr = new long[9];
	for (int i = 1; i <= 8; i++) {
	    arr[i] = nextLong();
	}
	leaveMax4(arr);

	long sum = 0;
	long safeSum = maxSum - 10000;
	if (safeSum > 0) {
	    for (int i = arr.length - 1; i >= 1; i--) {
		long cnt = (safeSum - sum) / i;
		boolean done = false;
		if (cnt <= arr[i]) {
		    done = true;
		}
		cnt = Math.min(cnt, Math.max(0, arr[i]-8));
		sum += cnt * i;
		arr[i] -= cnt;
		if (done) {
		    break;
		}
	    }
	}
	System.out.println(go(arr, sum, maxSum, 8));
    }

    private static long go(long[] arr, long sum, long maxSum, int ind) {
	long max = sum;
	for (long i = 0; i <= arr[ind]; i++) {
	    long v = sum + i * ind;
	    if (v == maxSum) {
		return maxSum;
	    } else if (v > maxSum) {
		break;
	    } else {
		if (ind > 1) {
		    v = go(arr, v, maxSum, ind - 1);
		}
		if (v == maxSum) {
		    return maxSum;
		}
		if (v > max) {
		    max = v;
		}
	    }
	}
	return max;
    }

    private static void leaveMax4(long[] arr) {
	for (int i = 1; i < arr.length; i++) {
	    if (arr[i] > 0) {
		for (int j = i + 1; j < arr.length; j++) {
		    if (arr[j] > 0) {
			int mod = j % i;
			if (mod == 0) {
			    int x = j / i;
			    if (arr[i] >= x - 1) {
				arr[i] += x * arr[j];
				arr[j] = 0;
			    }
			}
		    }
		}
	    }
	}
	int count = 0;
	for (int i = 1; i < arr.length; i++) {
	    if (arr[i] > 0) {
		count++;
	    }
	}
	if (count > 4) {
	    throw new RuntimeException();
	}
    }

    public static void main(String[] args) throws Exception {
	try {
	    fastReader = new FastReader(System.in);
	    systemOut = new BufferedOutputStream(System.out);
	    solve();
	} finally {
	    systemOut.close();
	}
    }

    private static FastReader fastReader = null;
    private static BufferedOutputStream systemOut = null;

    public static void print(Object obj) {
	print(obj.toString());
    }

    public static void print(String str) {
	try {
	    systemOut.write(str.getBytes("utf-8"));
	} catch (Exception ex) {
	    throw new RuntimeException(ex);
	}
    }

    public static void println(Object obj) {
	println(obj.toString());
    }

    public static void println(String str) {
	try {
	    print(str);
	    systemOut.write('\n');
	} catch (Exception ex) {
	    throw new RuntimeException(ex);
	}
    }

    public static String next() {
	return fastReader.readNextToken(false);
    }

    public static String nextLine() {
	return fastReader.readNextToken(true);
    }

    public static int nextInt() {
	return Integer.parseInt(fastReader.readNextToken(false));
    }

    public static long nextLong() {
	return Long.parseLong(fastReader.readNextToken(false));
    }

    public static double nextDouble() {
	return Double.parseDouble(fastReader.readNextToken(false));
    }

    static class FastReader {
	private byte[] buf = new byte[65536];
	private int ind = 0;
	private int maxInd = -1;
	private InputStream is = null;
	private boolean eof = false;
	private boolean lastCharRead = false;

	public FastReader(InputStream is) {
	    this.is = is;
	}

	public String readNextToken(boolean endOfLine) {
	    try {
		StringBuilder sb = new StringBuilder();
		boolean found = false;
		while (true) {
		    if (lastCharRead) {
			return null;
		    } else if (ind > maxInd) {
			if (eof) {
			    lastCharRead = true;
			} else {
			    fillBuffer();
			}
		    }
		    byte b = '\n';
		    if (!lastCharRead) {
			b = buf[ind++];
		    }

		    if (b == '\r') {
			// ignore
		    } else if ((b == '\n' && endOfLine) || (Character.isWhitespace(b) && !endOfLine)) {
			if (found) {
			    break;
			}
		    } else {
			sb.append((char) b);
			found = true;
		    }
		}
		return sb.toString();
	    } catch (Exception ex) {
		throw new RuntimeException(ex);
	    }
	}

	private void fillBuffer() {
	    try {
		int read = is.read(buf, 0, buf.length);
		if (read < buf.length) {
		    eof = true;
		}
		ind = 0;
		maxInd = read - 1;
	    } catch (Exception ex) {
		throw new RuntimeException(ex);
	    }
	}
    }
}
