#include <fstream>
#include <algorithm>
#define Nmax 5009
#define Gmax 10009

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n,d[3][Gmax],weight,x,price,G;

void Solve() {

    f>>n>>G;
    int line1=2;
    int line2=1;
    for (int i=1; i<=n; ++i) {

        f>>weight>>price;

        line1=3-line1;
        line2=3-line2;

        for (int j=1; j<=G; ++j) {

            d[line1][j]=d[line2][j];

            if (weight<=j) {

                d[line1][j]=max( d[line1][j], d[line2][j-weight] + price );
            }
        }
       // for (int j=1; j<=G; ++j) g<<d[line1][j]<<' ';
        //g<<'\n';
    }

    g<<d[line1][G]<<'\n';
}

int main() {

    Solve();

    f.close(); g.close();
    return 0;
}