#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[2][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[1][j]=dp[0][j];
else
if(dp[0][j] > dp[0][j-gr] + cost)
dp[1][j]=dp[0][j];
else
dp[1][j]=dp[0][j-gr] + cost;
}
for(j=1;j<=g;j++)
dp[0][j]=dp[1][j];
}
h<<dp[1][g]<<"\n";
}
int main()
{
citire();
DP();
return 0;
}