#include <bits/stdc++.h>
#define L 1005
#define LL 10005
#define INF 1000000001
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");

int n, g, w[L], p[L], dp[LL];

int main() {
  fin >> n >> g;
  for (int i = 1; i <= n; i++)
    fin >> w[i] >> p[i];
  for (int i = 0; i <= 2 * g; i++)
    dp[i] = INF;
  dp[0] = 0;
  for (int i = 1; i <= n; i++)
    for (int x = 2 * g; x >= w[i]; x--)
      dp[x] = min(dp[x], dp[x - w[i]] + p[i]);
  int ans = INF;
  for (int i = g; i <= 2 * g; i++)
    ans = min(ans, dp[i]);
  fout << ans << "\n";
  return 0;
}