#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("energii.in");
ofstream fout("energii.out");

int n, w;
struct centrala{
    int energieProdusa;
    int cost;
    }v[1003];

void readAndSolve(void);

int main(){
    readAndSolve();
    fin.close();
    fout.close();
    }

void readAndSolve(void){
    int energ, cost, i, k = 0;
    int dp[2][5003];
    fin>>n>>w;
    while(n--){
        fin>>energ>>cost;
        for(i = w; i >= 1; i--){
            if(dp[1 - k][i] != 0 && i - energ >= 0){
                dp[k][i] = min(dp[1 - k][i], cost + dp[1 - k][i - energ]);
                if(dp[k][i] < i)
                    dp[k][i] = 0;
                }
            else if(i - energ < 0)
                dp[k][i] = dp[1 - k][i];
            else if(dp[1 - k][i] == 0 && i - energ >= 0 && energ >= i)
                dp[k][i] = cost;
            }
        //for(int u = 1; u <= w; u++)
        //    cout<<dp[k][u]<<" ";
        //cout<<"\n";
        k = 1 - k;
        }
    k = 1 - k;
    fout<<dp[k][w];
    }