T = int(input())
n = int(input())
c = list(map(int, input().split()))
v = list(map(int, input().split()))
wv = []

for ci, vi in zip(c, v):
    while vi > 0:
        wv.append((ci, vi))
        vi = vi // 2

N = len(wv)
dp = [[0 for _ in range(T+1)] for _ in range(N+1)]

for i in range(N):
    wi, vi = wv[i]
    
    for j in range(T+1):
        if j - wi >= 0:
            dp[i+1][j] = max(dp[i][j-wi] + vi, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
            
print(dp[N][T])