#include<fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
long v[5001];
int n,gr, w[10001],p[10001];
int rucsac()
{
    int i,j;
    for(i=1;i<=n;++i)
        for(j=gr;j>=w[i];j--)
        v[j]=max(v[j],v[j-w[i]]+p[i]);
    return v[gr];
}
int main()
{
    f>>n>>gr;
    for(int i=1;i<=n;++i)
        f>>w[i]>>p[i];
    int k=rucsac();
    g<<k;
}