#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
struct OBIECT{
    int g, val;
}V[5001];
/*int N, A[5001][10001];
int DP(int poz, int g){
    if(poz > N)
        return 0;
    if( A[poz][g] > 0 )
        return A[poz][g];
    int x1, x2;
    x1 = DP(poz+1,g);//nu iau obiectul
    if(g >= V[poz].g )//verific daca il pot lua
        x2 = DP(poz+1,g-V[poz].g) + V[poz].val;
    else
        x2 = -1;
    if( x1 < x2 )
        x1 = x2; //salvez in x1 val maxima
    A[poz][g] = x1;
    return x1;
}*/
int A[2][10001];
int max(int a, int b){
    if(a > b)
        return a;
    return b;
}
int main()
{
    int i, j, gmax, n;
    f >> n >> gmax;
    for(i = 1; i <= n; i++)
        f >> V[i].g >> V[i].val;
    //g << DP(1, gmax);
    for(j = 0; j <= gmax; j++)
        if( j >= V[n].g )
            A[1][j] = V[n].val;
        else
            A[1][j] = 0;
    for( i = n - 1; i >= 1; i-- ){
        for(j = 0; j <= gmax; j++ ){
            if( j >= V[i].g )
                A[0][j] = max( A[1][j], A[1][j-V[i].g] + V[i].val );
            else
                A[0][j] = A[1][j];
        }
        for(j = 1; j <= gmax; j++)
            A[1][j] = A[0][j];
    }
    g << A[1][gmax];
    return 0;
}