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, r[0][0]+1):
        for j in range(G, 0, -1):
            if j-r[i][0] >= 0:
                v[j] = max(v[j], v[j-r[i][0]] + r[i][1])
    return v[G]


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