#include <bits/stdc++.h>
#define INF 1<<30
#define nmax 50001
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,s,x,y,c,d[nmax],m,i,k,min1,gr,l,nod,fr[nmax],ciclu;
int w[nmax],p[nmax],optim[nmax*2],sol,j;

int main()
{   f>>n>>gr;
for(i=1;i<=n;i++)
{
    f>>w[i]>>p[i];

}

optim[0]=0;
sol=0;

for(i=1;i<=n;i++)
{
    for(j=gr-w[i];j>=0;j--)
    if(optim[j+w[i]]<optim[j]+p[i])
    {
        optim[j+w[i]]=optim[j]+p[i];
        if(optim[j+w[i]]>sol)
            sol=optim[j+w[i]];
    }
}
    g<<sol;

    return 0;
}