t = int(input())
n = int(input())
C = list(map(int, input().split()))
V = list(map(int, input().split()))
dp = [-1]*(t+1)
dp[0] = 0
for c, v in zip(C, V):
    for i in reversed(range(t+1)):
        if dp[i] == -1:
            continue
        j = i+c
        cur = v
        s = v
        while j <= t:
            dp[j] = max(dp[j], dp[i]+s)
            j += c
            cur //= 2
            s += cur
            if cur == 0:
                break
print(max(dp))