#include <iostream>
#include <fstream>

#define N 5050

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n,c,p[N],g[N],cost[N][N], m1[N][N], m2[N][N];

void citire()
{
    fin>>n;
    fin>>c;

    for(int i=0;i<n;i++)
        fin>>g[i]>>p[i];
        /*
    for(int i=0;i<n;i++)
        fin>>g[i];*/
}

void Complet_Cost()
{
    for(int j=0;j<c;j++)
        if(j==g[0] && g[0]<=c)
            cost[0][j]=p[0],
            m1[j][m1[j][0]++]=0;
        else
            m1[j][0]=0;


    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=c;j++)
        {
            int maxx=-1, option=0;
            if(j==g[i] && g[i]<=c)
                if(maxx < p[i])
                {
                    maxx = p[i];
                    option=1;
                }

            if(maxx < cost[i-1][j])
            {
                maxx = cost[i-1][j];
                option=2;
            }

            if(g[i]<j && j<=c)
                if(maxx < cost[i-1][j-g[i]] + p[i])
                {
                    maxx = cost[i-1][j-g[i]] + p[i];
                    option=3;
                }
            cost[i][j]=maxx;
/**
            switch (option)
            {
                    case 1 :
                    {
                        m2[j][0]++;
                        m2[j][m2[j][0]]=i;
                        break;
                    }
                    case 2 :
                    {
                        for(int k=1;k<=m1[j][0];k++)
                        {
                            m2[j][0]=m1[j][0];
                            m2[j][k]=m1[j][k];
                        }
                        break;
                    }
                    case 3 :
                    {
                        for(int k=1;k<=m1[j-g[i]][0];k++)
                        {
                            m2[j][0]=m1[j-g[i]][0];
                            m2[j][k]=m1[j-g[i]][k];
                        }
                        m2[j][m2[j][0]++]=i;
                        break;
                    }
            }
 */

        }

/**
        fout <<" ___________________________________________________\n";
        for(int q=0;q<=c;q++)
        {   for(int w=0;w<=m1[q][0];w++)
                fout <<m1[q][w]<< " ";
            fout<<"\n";
        }
*/

            for(int q=0;q<=c;q++)
                for(int w=0;w<=m2[q][0];w++)
                    m1[q][w]=m2[q][w];
            for(int q=0;q<=c;q++)
                m2[q][0]=0;

    }
/**

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=c;j++)
            cout<<cost[i][j]<<" ";
        cout<<endl;
    }

    cout <<"\n\n\n";

    for(int q=0;q<=c;q++)
        {for(int w=0;w<=m1[q][0];w++)
            cout <<m1[q][w]<< " ";
        cout<<"\n";
        }
*/
    fout << cost[n-1][c]<<"\n";
/**
    for(int i=1;i<=m1[c][0];i++)
        fout << m1[c][i]+1<<" ";
*/
}


int main()
{
    citire();
    Complet_Cost();
    return 0;
}