#include <bits/stdc++.h>

using namespace std;

ifstream fin("energii.in");
ofstream fout("energii.out");
int target,n;
int dp[1005][5005];
int energie[1005];
int cost[1005];
int maxcost[1005];
int main()
{
    int i;
    fin>>n>>target;
    for(int i=1;i<=n;i++)
        fin>>energie[i]>>cost[i];
    for(int i=1;i<=n;i++)
        maxcost[i]=cost[i]+maxcost[i-1];
    for(i=1;i<=n&&maxcost[i-1]<target;i++)
    {
        for(int j=1;j<=min(energie[i],min(maxcost[i],target));j++)
            dp[i][j]=dp[i-1][j];
        for(int j=energie[i];j<=min(maxcost[i],target);j++)
            dp[i][j]=max(max(dp[i-1][j],dp[i][j-1]),dp[i-1][j-energie[i]]+cost[i]);
    }
        for(int j=energie[i];j<=min(maxcost[i],target);j++)
            dp[i][j]=max(max(dp[i-1][j],dp[i][j-1]),dp[i-1][j-energie[i]]+cost[i]);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=target;j++)
            if(dp[i][j]==0) dp[i][j]=1e9;
    for(;i<=n;i++)
        for(int j=energie[i]+1;j<=target;j++)
        {

            dp[i][j]=min(dp[i-1][j],dp[i-1][j-energie[i]]+cost[i]);
        }
    fout<<dp[n][target];

    return 0;
}