#include<fstream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

ifstream f("rucsac.in");
ofstream h("rucsac.out");

vector < pair <int,int> > a;

int dp[5005][10005];
int n,g;

void citire()
{
    int i,x,y;
    f>>n>>g;
    for(i=0;i<n;i++){
        f>>x>>y;
        a.push_back(make_pair(x,y));
    }
}

void DP()
{
    int i,j,gr,cost;
    for(i=1;i<=n;i++){
        gr=a[i-1].first;
        cost=a[i-1].second;
        for(j=1;j<=g;j++){
            if(j<gr)
                dp[i][j]=dp[i-1][j];
            else
                if(dp[i-1][j] > dp[i-1][j-gr] + cost)
                    dp[i][j]=dp[i-1][j];
                else
                    dp[i][j]=dp[i-1][j-gr] + cost;
                        }
                    }
    h<<dp[n][g]<<"\n";
}

int main()
{
    citire();
    DP();
    return 0;
}