t = int(input())
n = int(input())
C = list(map(int, input().split()))
V = list(map(int, input().split()))
dp = [0] * (t + 1)
for c, v in zip(C, V):
    while v > 0:
        for i in range(t, c - 1, -1):
            dp[i] = max(dp[i], dp[i - c] + v)
        v >>= 1
print(dp[-1])