#include <iostream>
#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int i,n,j,w[5005],v[5005],dp[5005][5005],gmax,max1;
int main()
{f>>n;
f>>gmax;

for(i=1;i<=n;i++){f>>w[i]>>v[i];}

for(i=1;i<=n;i++)
for(j=1;j<=gmax;j++){
dp[i][j]=dp[i-1][j];
    if(j>=w[i]){
    dp[i][j]=max(dp[i][j],v[i]);
    if(dp[i-1][j-w[i]]!=0){dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);}
    }
}
g<<dp[n][gmax];

    return 0;
}