#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("rucsac.in");
ofstream g ("rucsac.out");
int a[10000],n,i,j,gmax,lmax,x,y;
void initializare ()
{
    for(i=1;i<=gmax;i++)
    a[i]=-1;
}
int main()
{ f>>n>>gmax;
initializare();
f>>x>>y;
lmax=x;
a[x]=y;
for(i=2;i<=n;i++)
    {
        f>>x>>y;
        for(j=lmax;j>=0;j--)
        {
            if(a[j]!=-1)
            {
                a[x+j]=max(y+a[j],a[x+j]);
                lmax=max(lmax,x+j);
            }
        }

    }
    for(i=gmax;i>0;i--)
    {
      if(a[i]!=-1)
      {
          g<<a[i]<<" ";break;
      }
    }
    return 0;
}