rod cutting problem

l = int(input())
n = int(input())
ls = {0:0}
for i in range(n):
    length, value = [int(j) for j in input().split()]
    if length <= l and value > 0:
        ls[length] = value

c = 1
while c <= l:
    groups = [ls[r]+ls[c-r] for r in range(round(c//2)+1) if r in ls and c-r in ls]
    if groups:
        ls[c] = max(groups)
    c += 1

print(max(ls.values()))