v,n=map(int,input().split())
c=[0]*n
w=[0]*n
dp=[0]*(v+1)
for i in range (n):
    w[i],c[i]=map(int,input().split())
for i in range(n):
    for j in range(w[i],v+1):
        dp[j]=max(dp[j],dp[j-w[i]]+c[i])
print(dp[v])