def read_data():
    T = int(input())
    N = int(input())
    cs = list(map(int, input().split()))
    vs = list(map(int, input().split()))
    return T, N, cs, vs

def solve(T, N, cs, vs):
    dp = [0] * (T + 1)
    for c, v in zip(cs, vs):
        new_dp = dp[:]
        cc = c
        cv = v
        while v and cc <= T:
            for new_i, dpi in enumerate(dp[:-cc], cc):
                if dpi or new_i == cc:
                    new_val = dpi + cv
                    if new_val > new_dp[new_i]:
                        new_dp[new_i] = new_val
            cc += c
            v >>= 1
            cv += v
        dp = new_dp
    return max(dp)

T, N, cs, vs = read_data()
print(solve(T, N, cs, vs))