#include <fstream>

using namespace std;

int w[5005], p[5005], v[10005],a[10005];

int n,gmax,i,j,Max;

int main() {
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    f>>n>>gmax;
    for(i=1;i<=n;i++)
        f>>w[i]>>p[i];
    v[w[1]]=p[1];
    for(i=2;i<=n;i++) {
        for(j=0;j<=gmax;j++)
            if(w[i]<=j)
                a[j] = max(v[j],v[j-w[i]]+p[i]);
            else
                a[j]=v[j];
        for(j=0;j<=gmax;j++)
            v[j]=a[j];
    }
    for(i=0;i<=gmax;i++)
        if(a[i]>Max)
            Max=a[i];
    g<<Max<<"\n";
    return 0;
}