#include <fstream>
#include <algorithm>
#define mult (1<<30)
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");

int G,W,E[1002],C[1002],dp[2][5004];
bool u = false;
int main(){
fin >> G >> W;
for(int i = 0;i<G;i++){
        fin >> E[i] >> C[i];        
}
for(int i = 0;i<2;i++)
        for(int j = 0;j<=W;j++) dp[i][j] = mult;

for(int i = 0;i<G;i++)
        for(int j = 1;j<=W;j++){
                if(E[i] <= j) dp[u][j] = min(dp[!u][j],C[i]);else{
                        dp[u][j] = min(dp[!u][j-E[i]]+C[i],dp[!u][j]);                       
                }
                u = !u;
        }
fout << dp[!u][W];
    return 0;    
}