#include <iostream>
#include <fstream>

using namespace std;

ifstream in ("energii.in");
ofstream out ("energii.out");

#define MIN(a , b) ((a < b) ? a : b)
int const nmax = 5001;
int const inf = 1000000000;
int dp[5 + nmax];

int main()
{
  int n , k;
  in>>n>>k;
  for(int i = 1 ; i <= nmax ;i++)
    dp[i] = inf;
  dp[0] = 0;
  int sum = 0;
  for(int i = 1 ; i <= n ;i++){
    int a , b;
    in>>a>>b;
    sum += a;
    for(int j = MIN(k , sum) ; a <= j ;j--){
      dp[j] = MIN(dp[j] , dp[j - a] + b);
    }
  }
  out<<dp[k];
  return 0;
}