#include <cstdio>
using namespace std;

int Gmax,n,k=1,g[5001],C[5001],G,Cost[10001][10001];

int main(){

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

    scanf("%d%d",&n,&Gmax);
    for(int i=1;i<=n;i++)
    scanf("%d%d",&g[i],&C[i]);

        for(int i=1;i<=n;i++,k=3-k)
            for(G=1;G<=Gmax;G++){
                Cost[3-k][G] = Cost[k][G];
                if(g[i]<=G)
                    Cost[3-k][G] = Cost[3-k][G] > Cost[k][G-g[i]]+C[i] ? Cost[3-k][G]: Cost[k][G-g[i]]+C[i];
            }

printf("%d",Cost[k][Gmax]);
return 0;
}