#include <fstream>
#include<algorithm>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

int n,g,w[5005], p[5005],d1[10005],d2[10005],i,j,maxim;

int main () {

    fin>>n>>g;
    for (i=1;i<=n;i++)
        fin>>w[i]>>p[i];

    d1[w[1]]=p[1];

    for (i=2;i<=n;i++) {

        for (j=0;j<=g;j++)
            if (w[i]<=j)
                d2[j] = max (d1[j], d1[j-w[i]]+p[i]);
            else
                d2[j] = d1[j];
        for (j=0;j<=g;j++)
            d1[j]=d2[j];
    }

    for (i=0;i<=g;i++)
        if (d1[i]>maxim)
            maxim=d1[i];

    fout<<maxim<<"\n";

    return 0;
}