#include <bits/stdc++.h>
using namespace std;
const int gmax=1001;
const int wmax=5001;
const int valmax=10001;
int dp[2][wmax],g[gmax],c[gmax],w,n;
ifstream fin("energii.in");
ofstream fout("energii.out");
int main()
{
    int i;
    fin>>n>>w;
    for(int i=1;i<=n;i++)
        fin>>g[i]>>c[i];
    int L0=0,L1=1;
    for(int i=0;i<=w;i++)
        dp[L0][i]=1000000;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=w;j++)
            if(j>=g[i])
                dp[L1][j]=min(dp[L0][j],dp[L0][j-g[i]]+c[i]);
        else dp[L1][j]=min(dp[L0][j],c[i]);
        L0=1-L0;
        L1=1-L1;
    }
    fout<<dp[L0][w]<<"\n";
    return 0;
}