#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[Nmax][Gmax],w[Nmax],p[Nmax],maxim;

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

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

    return 0;
}