#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f("rucsac.in");
    ofstream h("rucsac.out");
  long int g,c,x[20000],z[20000],n,r,v,i,j,max=0;

    f>>n>>r;

    for(i=1;i<=2*r;i++)
        {x[i]=0;
       z[i]=0;
    }
    for(i=1;i<=n;i++)
    {    f>>g>>c;
    if(x[g]<c) x[g]=c;

for(v=1;v<=r;v++)
{
                     if (z[v]!=0)
                          if(z[v]+c>x[g+v])  x[g+v]=z[v]+c;}

               for(v=1;v<=r;v++)
                   {z[v]=x[v];  cout<<z[v];}}


         for(i=1;i<=r;i++)
          if(z[i]>max) max=z[i];
            h<<max;
}