#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
long long a[50001],gm,gr[50001],v[50001],i,j,maxim;
int n;
int main()
{

    f>>n>>gm;
for(i=1;i<=n;i++)
    f>>gr[i]>>v[i];

for(i=1;i<=n;i++)
for(j=gm-gr[i];j>=0;j--)
{if(a[j+gr[i]]<a[j]+v[i])
    a[j+gr[i]]=a[j]+v[i];
    if(a[j+gr[i]]>maxim)
        maxim=a[j+gr[i]];
    }

    g<<maxim;
}