def bin(n,size=0):
    if n in [0,1]:
        return str(n)
    return (bin(n / 2) + str(bin(n % 2))).zfill(size)

def dec(n,x=0):
    d = int(n[-1]) * (2**x)
    if len(n) == 1:
        return d
    return dec(n[:-1],x+1) + d
    

inp = open('DATA3.txt','r')
out = open('OUT3.txt','w')
for x in range(5):
    size = int(inp.readline())
    songs = []
    for _ in range(int(inp.readline())):
        songs.append([int(x) for x in inp.readline().split(' ')[1:]])
    n = dec('1' * len(songs))
    best = 0
    for y in range(n+1):
        cursize = 0
        currating = 0
        for z,s in zip(bin(y).zfill(len(songs)),songs):
            if z == '1':
                cursize += s[1]
                if cursize > size:
                    break
                currating += s[0]
                if currating > best:
                    best = currating
    out.write('%s\n' % best)
out.close()