#include <iostream>
#include<stdio.h>
#include<limits.h>
#define IMAX 10000
using namespace std;
int g,w;
int i,j;
int a[IMAX],b[IMAX],d[IMAX];
int maxfol;
int minim=INT_MAX;
void citire()
{
  freopen("energii.in","r",stdin);
  freopen("energii.out","w",stdout);
  scanf("%d",&g);
  scanf("%d",&w);
for(i=0;i<g;i++)
    scanf("%d %d",&a[i],&b[i]);
    d[0]=0;
}
void rezolvare()
{
    for(i=0;i<g;i++)
        for(j=maxfol;j>=0;j--)
            if((d[j]!=0||j==0)&&d[j]+b[i]>d[j+a[i]])
            {
                if(j+a[i]>=w&&d[j]+b[i]<minim)
                    minim=d[j]+b[i];
                d[j+a[i]]=d[j]+b[i];
                if(j+a[i]>maxfol)
                    maxfol=j+a[i];
            }

}
void afisare()
{
    int i;
  /*  for(i=1;i<=w;i++)
        printf("%d ",d[i]);*/
          printf("%d\n",minim);
}
int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}