#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,l,maxim=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[i][j]=mat[i-1][j];
}
for(j=vet[i];j<=g;j++){
    if(mat[i-1][j]>mat[i-1][j-vet[i]]+profit[i]&&mat[i-1][j]>0)
    mat[i][j]=mat[i-1][j];
    else if(mat[i-1][j-vet[i]]>0)
            mat[i][j]=mat[i-1][j-vet[i]]+profit[i];
if(i==n&&mat[i][j]>maxim)
    maxim=mat[i][j];
}
}
out<<maxim-1;
}