T=int(input())
N=int(input())
C=list(map(int,input().split()))
V=list(map(int,input().split()))
inf=1<60
dp=[-inf]*(T+1)
dp[0]=0
for c,v in zip(C,V):
    for _ in range(10):
        for t in range(T,c-1,-1):
            dp[t]=max(dp[t],dp[t-c]+v)
        v//=2
ans=max(dp)
print(ans)