#include <bits/stdc++.h>
#define ull unsigned long long
#define FILES freopen("energii.in","r",stdin);\
              freopen("energii.out","w",stdout);
#define CMAX 15485863
#define fastio std::ios_base::sync_with_stdio(NULL),cin.tie(NULL),cout.tie(NULL);
#define mp make_pair
#define INF 1e18
#define mod 666013
#define ll long long
#define SMAX 300
#define MAX 1000
#define pb push_back
#define add emplace_back
#define void inline void
#define int ll
using namespace std;
int n,g,dp[MAX+5],best = 1e9,s;
pair<int,int> v[MAX+5];
bool cmp(pair<int,int> a,pair<int,int>b)
{
    return a.second < b.second;
}
signed main()
{
    fastio
    FILES
    cin >> n >> g;
    for(int i = 1;i <= n; ++i)
        cin >> v[i].first >> v[i].second;
    sort(v+1,v+1+n,cmp);
    for(int i = 1;i <= g; ++i)
        dp[i] = 1e9;
    for(int i = 1;i <= n; ++i)
    {
        s += v[i].first;
        for(int j = g - v[i].first + 1; j <= g; ++j)
           best = min(best,dp[j] + v[i].second);
        for(int j = min(s,g);j >= v[i].first; --j)
            dp[j] = min(dp[j],dp[j-v[i].first]+v[i].second);
    }
    cout << min(best,dp[g]);
}