t = int(input())
n = int(input())
c = list(map(int, input().split()))
v = list(map(int, input().split()))
mc = min(c)
for i in range(n):
    w = v[i]//2
    while w:
        v.append(w)
        c.append(c[i])
        w //= 2
n = len(v)
dp = [[0]*(t+1) for _ in range(n+1)]
for i in range(n)[::-1]:
    for j in range(t+1):
        dp[i][j] = dp[i+1][j]
        if j+c[i] <= t:
            dp[i][j] = max(dp[i][j], v[i]+dp[i+1][j+c[i]])
print(dp[0][0])