#include <fstream>
#include <iostream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int const gmax=10007, lmax=5007;
int dp[3][gmax];
int n,gtotal;
int profit[lmax];
int kg[lmax];
int main()
{
    fin>>n>>gtotal;
    for(int i=1;i<=n;i++)
    {
        fin>>kg[i]>>profit[i];
    }
    int altern=0;
    for(int i=1;i<=n;i++)
    {

        altern=1-altern;
        for(int j=1;j<=gtotal;j++)
        {
//            dp[0][j] = dp[1][j];
            if(kg[i] <= j)
//            dp[1][j]=max(dp[0][j],dp[0][j-kg[i]]+profit[i]);
                dp[altern][j]=max(dp[1-altern][j],dp[1-altern][j-kg[i]]+profit[i]);
            else
                dp[altern][j] = dp[1-altern][j];
        }
    }
//    int mxm = 0;
//    for(int i = 1; i <= gtotal; i ++) {
//        if(dp[altern][i] > mxm)
//            mxm = dp[altern][i];
//    }
//    fout<<mxm;
//    fout << dp[1][gtotal];
    fout << dp[altern][gtotal];
    fin.close();
    fout.close();
    return 0;
}