#include<fstream>
#include<queue>
#include<iostream>
#include<map>
#include<algorithm>
#include<unordered_map>
#include<stack>
#define DN 1005
#define DM 5005
#define x first
#define y second
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
int n,m,dp[DN][DM],mi=1e9;
pair<int,int>a[DN];
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        fin>>a[i].x>>a[i].y;
    for(int i=0;i<=n;i++)
        for(int j=1;j<=m;j++)
            dp[i][j]=1e9;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
        {
            if(a[i].x+j>=m)
                mi=min(mi,dp[i-1][j]+a[i].y);
            if(a[i].x+j<=m)
                dp[i][j+a[i].x]=min(dp[i][j+a[i].x],dp[i-1][j]+a[i].y);
        }
    fout<<mi;
}