#include <cstdio>
#include <cstring>

using namespace std;

long n,g,i,a[10001],b[10001],j,gi,pi;

int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);

    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("%ld\n",a[g]);

    return 0;
}