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
#!/usr/bin/env python2
"""
This file is part of https://github.com/cheran-senthil/PyRival
Copyright 2019 Cheran Senthilkumar <hello@cheran.io>

"""
from __future__ import division, print_function

import itertools
import os
import sys
from atexit import register
from io import BytesIO


class dict(dict):
    """dict() -> new empty dictionary"""

    def items(self):
        """D.items() -> a set-like object providing a view on D's items"""
        return dict.iteritems(self)

    def keys(self):
        """D.keys() -> a set-like object providing a view on D's keys"""
        return dict.iterkeys(self)

    def values(self):
        """D.values() -> an object providing a view on D's values"""
        return dict.itervalues(self)


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


range = xrange

filter = itertools.ifilter
map = itertools.imap
zip = itertools.izip

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

input = lambda: sys.stdin.readline().rstrip('\r\n')


def memoize(f):
    """ Memoization decorator for a function taking one or more arguments. """

    class memodict(dict):
        def __getitem__(self, *key):
            return dict.__getitem__(self, key)

        def __missing__(self, key):
            ret = self[key] = f(*key)
            return ret

    return memodict().__getitem__


def main():
    init_w = int(input())
    cnt = [int(i) for i in input().split()]

    dp_cnt = [min(cnt_i, 20) for i, cnt_i in enumerate(cnt)]
    greedy_cnt = [cnt_i - dp_cnt_i for cnt_i, dp_cnt_i in zip(cnt, dp_cnt)]

    i, w = 8, init_w
    while (i > 0) and (w > 0):
        w -= i * greedy_cnt[i - 1]
        if w < 0:
            w %= i
            for j in range(2):
                w += i if min(greedy_cnt[i - 1], dp_cnt[i - 1]) > j + 1 else 0

        i -= 1

    weights = reduce(list.__add__, (dp_cnt_i * [i + 1] for i, dp_cnt_i in enumerate(dp_cnt)))

    @memoize
    def solve(i, val):
        if val == 0:
            return True
        if i == 0:
            return False
        return solve(i - 1, val) or solve(i - 1, val - weights[i - 1])

    for val in range(min(w, sum(weights)), -1, -1):
        if solve(len(weights), val):
            print(init_w - w + val)
            break


if __name__ == '__main__':
    main()
