#include<bits/stdc++.h>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
struct ob{
    int w,p;
}v[5001];
int N,G,rez[10001];
int main()
{
    f>>N>>G;
    for(int i=1;i<=N;++i)f>>v[i].w>>v[i].p;
    for(int i=1;i<=N;++i)
        for(int j=G-v[i].w;j>=0;--j)
            if(rez[j]+v[i].p>rez[j+v[i].w])
                rez[j+v[i].w]=rez[j]+v[i].p;
    g<<rez[G];
    return 0;
}