#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int w[5001], p[5001];
int dp[3][10000];
int main()
{
    int n, g, pmax=0;
    fin>>n>>g;
    for(int i=1; i<=n; i++)
        fin>>w[i]>>p[i];
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=g; j++)
            dp[1][j]=dp[2][j];
        for(int j=1; j<=g; j++)
        {
            if(j>=w[i])
                dp[2][j]=max(dp[1][j], dp[1][j-w[i]]+p[i]);
            else
                dp[2][j]=dp[1][j];
            //cout<<dp[i][j]<<" ";
            if(i==n && dp[2][j]>pmax)
                pmax=dp[2][j];
        }
        //cout<<"\n";
    }
    fout<<pmax;

    return 0;
}