#include <bits/stdc++.h>

using namespace std;

int main()
{
    ifstream f("rucsac.in");
    ofstream c("rucsac.out");

    int n=0, G=0, x=0;
    f>>n>>G;
    int d[n][G] = {};
    int g[n+1]={};
    int val[n+1]={};
    for(int i=1; i<=n; ++i) f>>g[i]>>val[i];
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=G; ++j)
        {
            ///cout<<i<<":"<<j<<endl;
  /**          if(j < g[i]) {d[i][j] = d[(i-1)][j]; //cout<<d[i][j]<<" "<<endl;
            }
            //else { cout<<d[(i-1)][j]<<" "<<d[(i-1)][j-g[i]]<<"+"<<val[i]<<endl;}
            else d[i][j]=max(d[i-1][j], d[(i-1)][j-g[i]] + val[i]);
            cout<<d[i][j]<<" ";
**/
            if(j < g[i]) d[i&1][j] = d[(i-1)&1][j];
            else d[i&1][j]=max(d[(i-1)&1][j], d[(i-1)&1][j-g[i]] + val[i]);
           x=d[i&1][j];

        }
    }
    c<<x;
    return 0;
}