#include <fstream>

#define In "rucsac.in"
#define Out "rucsac.out"
#define Gmax 10001
using namespace std;
int dp[Gmax];
int main()
{
    int N, G, p, g,Last =0;
    ifstream f(In);
    f>>N>>G;
    while(N--)
    {
        f>>g>>p;
        for(int i = G;i;--i)
            if(i>=g)
                dp[i] = max(dp[i],dp[i-g]+p);
        if(Last+g<=G)
            Last+=g;
    }
    f.close();
    ofstream out(Out);
    out<<dp[G]<<"\n";
    out.close();
    return 0;
}