with open("rucsac.in", "r") as r:
    r = [[int(y) for y in x.split()] for x in r.read().split('\n')]


def rucsac(G):
    v = [0 for x in range(G+2)]
    for i in range(1, len(r)):
        for j in range(G, 0, -1):
            g = r[i][0]
            p = r[i][1]
            if j-g >= 0:
               v[j] = max(v[j], v[j-g] + p)
    return v[G]


with open("rucsac.out", "w") as w:
    w.write(str(rucsac(r[0][1])))