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