T = int(input())
N = int(input())
c = list(map(int, input().split()))
v = list(map(int, input().split()))
C, V = [], []
now = 1
for _ in range(10):
    for i in range(N):
        C.append(c[i])
        V.append(v[i]//now)
    now *= 2

N *= 10
inf = 10 ** 18
pre = [-inf] * (T + 1)
pre[0] = 0
for i in range(N):
    dp = [-inf] * (T + 1)
    for t in range(T + 1):
        dp[t] = max(dp[t], pre[t])
        if t - C[i] >= 0:
             dp[t] = max(dp[t], pre[t - C[i]] + V[i])
    dp, pre = pre, dp

print(max(pre))