#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
int seg,scg,l,a[2][10001],b[2][10001],x,g,w,eg,cg;
int main()
{
    fin>>g;
    fin>>w;
    fin>>eg>>cg;
    l=0;
    for(int j=2;j<=w;j++)
    {a[0][j]=eg;
     b[0][j]=cg;}
     for(int i=2;i<=g;i++,l=1-l)
     {
         fin>>eg>>cg;
         for(int j=2;j<=w;j++)
         {
                 if(eg>=j&&a[1-l][j]>=j)
                     {if(b[1-l][j]>cg)
                     {
                         a[l][j]=eg;
                         b[l][j]=cg;
                     }
                     else
                     {
                         a[l][j]=a[1-l][j];
                         b[l][j]=b[1-l][j];
                     }
                     }

             if(a[1-l][j]<j&&eg>=j)
             {
                 a[l][j]=eg;
                 b[l][j]=cg;
             }
             else if(a[1-l][j]>=j&&eg<j)
                {
                    a[l][j]=a[1-l][j];
                        b[l][j]=b[1-l][j];

                }
                else
                {
                    if(j-eg==1)
                    {
                        a[l][j]=eg+a[1-l][j-eg+1];
                        b[l][j]=cg+b[1-l][j-eg+1];
                    }
                    else
                    {
                        a[l][j]=eg+a[1-l][j-eg];
                        b[l][j]=cg+b[1-l][j-eg];
                    }

                }

         }
     }
     fout<<b[1-l][w];
    return 0;
}