#include<stdio.h>
#include<cstring>
int a[10001],b[10001];
int main()
{
 freopen("rucsac.in","r",stdin);
 freopen("rucsac.out","w",stdout);
 int n,g,i,j,gi,pi;
 scanf("%d%d",&n,&g);
 for(i=1;i<=n;i++)
        {
         scanf("%d%d",&gi,&pi);
         for(j=gi;j<=g;j++)
         {
          if(a[j]>=(a[j-gi]+pi))
                 b[j]=a[j];
          else
              b[j]=a[j-gi]+pi;
         }
         memcpy(a,b,sizeof(b));
        }
 printf("%d",a[g]);
 return 0;
}