def readData(fileIn, weight, price):
    with open(fileIn, "r") as f:
        data = f.read()
        lines = data.split('\n')
        firstLine = lines[0].split()
        n = int(firstLine[0])
        gmax = int(firstLine[1])
        for index in range(1, len(lines)):
            line = lines[index].strip().split()
            weight.append(int(line[0]))
            price.append(int(line[1]))
    return n, gmax


if __name__ == '__main__':

    fileIn = "rucsac.in"
    fileOut = "rucsac.out"
    weight = []
    price = []
    n, gmax = readData(fileIn, weight, price)
    line1 = [0] * (gmax + 1)
    line2 = [0] * (gmax + 1)
    for i in range(n):
        for j in range(gmax + 1):
            if weight[i] <= j:
                if line2[j] < line1[j - weight[i]] + price[i]:
                    line2[j] = line1[j - weight[i]] + price[i]
        line1.clear()
        line1.extend(line2)
    with open(fileOut, "w") as f:
        f.write(str(line2[gmax]) + '\n')