#include <fstream>
#include <iostream>
#define INF (1<<30)
using namespace std;

int N, W, dp[1010][5010], E[1010], C[1010]; bool viz[1010][5010];

int solve(int item, int energy){
    if (item==0 && energy>0)
        return INF;

    if (energy <=0)
        return 0;

    if (viz[item][energy])
        return dp[item][energy];

    viz[item][energy]=1;
    int x=solve(item-1,energy);
    int y=solve(item-1,energy-E[item])+C[item];
    dp[item][energy]=min(x,y);
    return dp[item][energy];
}

int main(){
    ifstream in("energii.in");
    ofstream out("energii.out");
    in >> N >> W;

    int i,j;
    for (i=1; i<=N; i++)
        in >> E[i] >> C[i];

    for (i=1; i<=N; i++)
        for (j=0; j<=W; j++)
            dp[i][j]=INF;

    out << solve(N,W);
    return 0;
}