T = int(input())
N = int(input())
C = list(map(int, input().split()))
V = list(map(int, input().split()))

dp = [0] * (T + 1)
for v, c in zip(V, C):
    while v:
        for i in reversed(range(c, T + 1)):
            dp[i] = max(dp[i], dp[i - c] + v)
        v //= 2

print(dp[T])