#include <cstdio>
using namespace std;

int Gmax,n,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++)
            for(G=1;G<=Gmax;G++){
                Cost[i][G] = Cost[i-1][G];
                if(g[i]<=G)
                    Cost[i][G] = Cost[i][G] > Cost[i-1][G-g[i]]+C[i] ? Cost[i][G]: Cost[i-1][G-g[i]]+C[i];
            }

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