infile = open('DATA4.txt','r')
outfile = open('OUT4.txt','w')

for prb in range(5):
    space = int(infile.readline())
    files = []
    numfiles = int(infile.readline())
    
    for i in range(numfiles):
        files = files + [[int(s) for s in infile.readline().split()]]
    #print files
    util = set([(0,0)])
    for sz, ut in files:
        newutil = set([(s+sz,u+ut) for s,u in util if s+sz <= space])
        #print newutil
        util = util | newutil
    #print util
    outfile.write(str(max([b for a,b in util]))+'\n')
    infile.readline()