#include <iostream>

using namespace std;
int n,k,minim=9999999;
pair<int,int> v[1005];
int ruc[150005],cost[15005];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>v[i].first>>v[i].second;
    }
    for(int i=1;i<=n;i++){
        for(int j=15000;j>=0;j--){
            if(cost[j]!=0 or j==0){
                cost[j+v[i].first]=max(cost[j+v[i].first],cost[j]+v[i].second);
            }
        }
    }
    for(int i=k;i<=15000;i++){
        if(cost[i]!=0){
            if(minim>cost[i])
                minim=cost[i];
        }
    }
    cout<<minim;
    return 0;
}