t = int(input())
n = int(input())
c = list(map(int, input().split()))
v = list(map(int, input().split()))
dp = [0] * (t + 1000)
for ci, vi in zip(c, v):
    for i in range(t, -1, -1):
        vnow = vi
        for j in range(i + ci, i + ci * 9 + 1, ci):
            dp[j] = max(dp[j], dp[j - ci] + vnow)
            vnow //= 2
print(dp[t])