#include <fstream>
#define maxim(a, b) (a)>(b) ? (a) : (b)
#define minim(a, b) (a)<(b) ? (a) : (b)
using namespace std;

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

int n, g, w, p, dp[10010], mx, from;

int main()
{
    in>>n>>g;
    for(register int i=1; i<=n; i++)
    {
        in>>w>>p;
        for(register int q=from; q>=0; q--)
            if(q==0 || dp[q])
                dp[q+w]=maxim(dp[q+w], dp[q]+p);
        from=minim(from+w,g);
    }
    for(register int i=1; i<=g; i++)
        mx=maxim(mx, dp[i]);
    out<<mx;
    return 0;
}