#!/usr/bin/env python3

# université pierre et marie curie - c. dürr - 2017
# http://www-desir.lip6.fr/~durrc/Iut/cpa/2017/tme5-progdyn/

# Sac à dos
# algorithme: programmation dynamique sur la grille
# complexité: O(n C)

from sys import stdin

def readint():
    return int(stdin.readline())

def readints():
    return map(int, stdin.readline().split())

def knapsack(p, v, C):
    """ p = poids des éléments, v = valeurs des éléments, C = capacité knapsack
    complexité : O(n C)

    problème:
        Opt[i][c] = valeur maximum d'un ensemble de {0,..,i} de poids total au plus c
        solution = Opt[n-1][C]
    cas de base:
        Opt[0][c] = 0 si c < p[0] et = v[0] sinon
    récursion:
        Opt[i][c] = max(Opt[i - 1][c], Opt[i - 1][c - p[i]] + v[i])  # attention au cas c < p[i]
    complexité:
        O(n*C) variables, évaluation en temps constant
        total = O(n*C)
    """
    n = len(v)
    assert n == len(p)
    Opt = [[0 for c in range(C + 1)] for i in range(n)]
    for c in range(p[0], C + 1):
        Opt[0][c] = v[0]
    for i in range(1, n):
        k = min(p[i], C)
        for c in range(k):
            Opt[i][c] = Opt[i-1][c]
        for c in range(k, C + 1):
            Opt[i][c] = max(Opt[i - 1][c], Opt[i - 1][c - p[i]] + v[i])
    return Opt[n-1][C]

n, C = readints()
p = []
v = []
for _ in range(n):
    pi, vi = readints()
    p.append(pi)
    v.append(vi)

print(knapsack(p, v, C))