#include <bits/stdc++.h>

using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
int a[5005][1005];
int main()
{int g,w,i,j,k,t,s,S;
struct energie
{
    int c,p;
};
energie v[1005];
fin>>g>>w;
t=INT_MAX;
s=0;
S=0;
for(i=1;i<=g;i++){
    fin>>v[i].c>>v[i].p;
    s=s+v[i].c;
    if(v[i].c<=w){
        S=S+v[i].c;
    }
}
if(s<w){
    fout<<-1;
}
else{
for(i=1;i<=g;i++){
    for(j=1;j<=w;j++){
        a[i][j]=a[i-1][j];
        if(v[i].c<=w){
a[i][j]=max(a[i-1][j],a[i-1][j-v[i].c]+v[i].p);
    }
    else{
        if(v[i].p<t){
            t=v[i].p;
        }
    }

    }
}
if(t<a[g][w] || S<w){
    fout<<t;
}
else{
    fout<<a[g][w];
}}
    return 0;
}