#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

const int NMAX = 5005;

int n, w;
pii v[NMAX];
int dp[NMAX];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL_DEFINE
  freopen (".in", "r", stdin);
#endif

  freopen ("energii.in", "r", stdin);
  freopen ("energii.out", "w", stdout);

  scanf ("%d\n%d\n", &n, &w);
  for (int i = 1; i <= n; ++i) {
    scanf ("%d %d\n", &v[i].fi, &v[i].se);
  }

  for (int i = 0; i <= w; ++i) dp[i] = (1 << 30);
  dp[0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = w; j >= v[i].fi; --j) {
      if (j + v[i].fi <= w) {
        dp[j + v[i].fi] = min (dp[j + v[i].fi], dp[j] + v[i].se);
      } else {
        dp[w] = min (dp[w], dp[j] + v[i].se);
      }
    }
    dp[v[i].fi] = min (dp[v[i].fi], v[i].se);
  }

  printf ("%d\n", dp[w]);

  fclose (stdin);
  fclose (stdout);
  return 0;
}