T,M = map(int,input().split(' ')) lis1 = [0] lis2 = [0] for i in range(M): a, b = map(int,input().split(' ')) lis1.append(a) lis2.append(b)

lis = [[0 for i in range(T+1)]for i in range(M+1)]

for i in range(1,M+1): for j in range(1,T+1): if j<lis1[i]: lis[i][j] = lis[i-1][j] else: lis[i][j] = max(lis[i-1][j], lis[i-1][j-lis1[i]]+lis2[i])

print(lis)

lis3 = [] for i in lis: lis3.append(max(i)) print(max(lis3))