#include <fstream>
#define IN "rucsac.in"
#define OUT "rucsac.out"
#define NMAX 5005
#define GMAX 10005

using namespace std;

ifstream in(IN);
ofstream out(OUT);

int n,g,profit[NMAX],gr[GMAX],castig1[GMAX],castig2[GMAX];

int main()
{
    in>>n>>g;
    int i,j,k;
    for (i=1;i<=n;i++)
        in>>gr[i]>>profit[i];
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=g;j++)
        {
            if(gr[i]<=j)
                if( profit[i] + castig1[j-gr[i]] > castig1[j] )
                    castig2[j]=castig1[j-gr[i]] + profit[i];
                else
                    castig2[j]=castig1[j];
            else
                castig2[j]=castig1[j];
        }
        for (k=1;k<=g;k++)
            castig1[k]=castig2[k];
    }
    out<<castig2[g];
    in.close();
    out.close();
    return 0;
}