#include<fstream>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

pair<int,int> dp[10000];
int p[5000],c[5000];



int main()
{
    int fete,s;
    cin>>fete>>s;

    for(int i=1;i<=fete;i++)
        {
            cin>>p[i]>>c[i];
        }
    //dinamica

    for(int i=1;i<=fete;i++)
        {
            for(int j=1;j<=s;j++)
                {
                    dp[j].second=dp[j].first;
                    if(c[i]<=j)
                        {
                            dp[j].second = max(dp[j].second,(dp[j-c[i]].first + p[i]));
                        }
                    for(int k=1;k<=fete;k++)
                        swap(dp[k].first,dp[k].second);
                }
        }
    cout<<dp[s].first;
    return 0;

}