T = int(input())
N = int(input())
lsc = list(map(int,input().split()))
lsv = list(map(int,input().split()))
lsvc = []
for i in range(N):
    c = lsc[i]
    v = lsv[i]
    while v > 0:
        lsvc.append([c,v])
        v //= 2
N = len(lsvc)
dp = [[0]*(T+1) for i in range(N+1)]
for i in range(N):
    for j in range(T+1):
        if j + lsvc[i][0] <= T:
            dp[i+1][j + lsvc[i][0]] = max(dp[i][j + lsvc[i][0]],dp[i][j]+lsvc[i][1])
        else:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[N][T])