#include <iostream>
#include <fstream>
#define Nmax 5001
#define Gmax 10001

using namespace std;

ifstream f("rucsac.in");
ofstream o("rucsac.out");

int i,n,s,g,dp[2][Gmax],w[Nmax],p[Nmax],maxim;

int main()
{
    f >> n >> g;
    for(i=1;i<=n;++i)
        f >> w[i] >> p[i];

        for(i=1;i<=n;++i){
    for(s=1;s<=g;++s){
            dp[i%2][s]=dp[(i-1+2)%2][s];
            if(s-w[i]>=0)
                dp[i%2][s]=max(dp[i%2][s],dp[(i-1+2)%2][s-w[i]]+p[i]);
            //cout << dp[i%2][s] << " ";
        }
        //cout << '\n';
    }
    o << max(dp[0][g],dp[1][g]) << '\n';

    return 0;
}