#include <fstream>
using namespace std;

int n,gmax,kg,va,i,j,maxi,ma;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

typedef struct ITEM { bool da; int val;};
ITEM v[1000100];

int main()
{
    f>>n>>gmax;
    v[0].da=1; //se pot obtine 0 kg
    ma=0;
    for(i=1; i<=n; i++)
    {
       f>>kg>>va;
       for(j=ma; j>=0; j--)
          if( v[j].da==1 ) //daca se pot obtine j kg
          {
              if( ma< j+kg ) ma=j+kg;
              if( v[j+kg].da==0)
              {
                v[j+kg].da=1; //se pot obtine pt prima data j+kg kilograme
                v[j+kg].val=v[j].val+va; //la j+kg kilograme avem valoarea *cat era* + ce am adaugat
              }
              else
                v[j+kg].val=min(v[j].val+va,v[j+kg].val+va); //la j+kg kilograme avem valoareain pluc cu ce am adaugat
          }
    }
    for( i=gmax; i>=0; i--)
       if( v[i].da==1 ) //se pot obtine i kg
          if( maxi < v[i].val)
            maxi=v[i].val;
   g<<maxi<<" ";
    for(i=1; i<=30; i++)
      // cout<<i<<" "<<v[i].da<<" "<<v[i].val<<endl;;

    return 0;
}