#include <bits/stdc++.h>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int const gmax=10007, lmax=5007;
int dp[2][gmax];
int n,gtotal;
int profit[lmax];
int kg[lmax];
void afis(int i)
{
    for(int j=1;j<=gtotal;j++)
    {
        cout<<dp[i][j]<<" ";
    }
    cout<<"\n";
}
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++)
        {
            if(j-kg[i]<0)
            {
                dp[altern][j]=dp[1-altern][j];
            }
            else dp[altern][j]=max(dp[1-altern][j],dp[1-altern][j-kg[i]]+profit[i]);
        }

        //afis(altern);
    }
    altern=1-altern;
    fout<<dp[altern][gtotal];
    fin.close();
    fout.close();
    return 0;
}