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