#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <unordered_map>
using namespace std;
/*解题思路:*/
int main(){
int n,p,a,b;
int cot[100000]={0};
int num[10000]={0};
int dp[100000]={0};
while(cin>>n>>p){
for(int i=0;i<n;++i){
cin>>a>>b; cot[i]=a; num[i]=b;
}
for(int i=0;i<n;i++){
for(int j=p;i>=cot[i];j--){
dp[j]=max(dp[j],dp[j-cot[j]]+num[j]);
}
}
cout<<p-dp[p]<<endl;
}
return 0;
}