#include <fstream>
using namespace std;
ifstream in("energii.in");
ofstream out("energii.out");
int n,k,e[1001],c[1001],dp[10000001];
int se,sc;
int main()
{ in>>n>>k;
  for(int i=1;i<=n;i++)
    in>>e[i]>>c[i],se+=e[i],sc+=c[i];
  se-=k;
  for(int i=1;i<=n;i++)
  { for(int j=se;j>0;j--)
    { if(j<e[i])
         dp[j]=dp[j];
      else
         dp[j]=max(dp[j],dp[j-e[i]]+c[i]);
    }
  }
  out<<sc-dp[se];
  in.close();
  out.close();
  return 0;
}