#include <fstream>
#include <vector>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
vector <pair<int,int> > v;
const int nmax=1e4;
int dp[2][nmax+5];
int n,g;
int main()
{
    in>>n>>g;
    v.push_back({0,0});
    for(int i=1; i<=n; i++)
    {
        int x,y;
        in>>x>>y;
        v.push_back({x,y});
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=g; j++)
        {
            if(v[i].first<=j)
                dp[i%2][j]=max(dp[(i-1)%2][j-v[i].first]+v[i].second,dp[(i-1)%2][j]);
            else
                dp[i%2][j]=dp[(i-1)%2][j];
        }
    out<<dp[n%2][g];
    return 0;
}