#include<iostream>
#include<fstream>

using namespace std;

int DP[5010][10010];

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

int main()
{
    int N, Gmax, val[5010], gr[5010], i,j;
    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(i==1)
            {
                if(j>=gr[i])
                    DP[i][j]=val[i];
                else
                    DP[i][j]=0;
            }
            else
            {
                if(j<gr[i])
                    DP[i][j]=DP[i-1][j];
                else
                {
                    DP[i][j]=max(DP[i-1][j], val[i] + DP[i-1][j-gr[i]]);
                }
            }
        }
    }

    out<<DP[N][Gmax];
}