#include<iostream>
#include<fstream>

using namespace std;

int DP[2][10010];

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

int main()
{
    int N, Gmax, val[5010], gr[5010], i,j,k=0,bec=1;
    in>>N>>Gmax;
    for(i = 1; i<=N; i++)
        in>>gr[i]>>val[i];
    for(i=1;i<=N;i++)
    {
        for(j=0;j<=Gmax;j++)
        {
            if(bec==1)
            {
                if(j>=gr[i])
                    DP[k][j]=val[i];
                else
                    DP[k][j]=0;
            }
            else
            {
                if(j<gr[i])
                    DP[k][j]=DP[1-k][j];
                else
                {
                    DP[k][j]=max(DP[1-k][j], val[i] + DP[1-k][j-gr[i]]);
                }
            }
        }
        if(bec==1)
            bec=0;
        k=1-k;
    }

    out<<DP[1-k][Gmax];
}