#include<bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int mat[5005][10005];
int vet[5005];
int profit[5005];
int main(){
int n,g,i,j;
in>>n>>g;
mat[0][0]=1;
for(i=1;i<=n;i++){
in>>vet[i]>>profit[i];
for(j=vet[i];j<=g;j++){
    if(mat[i-1][j]>mat[i-1][j-vet[i]]+profit[i])
    mat[i][j]=mat[i-1][j];
    else mat[i][j]=mat[i-1][j-vet[i]]+profit[i];

}
}
out<<mat[n][g]-1;
}