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

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