#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++){
if  (j>=w[i])if(dp[i-1][j]>=dp[i-1][j-w[i]]+v[i]) max1=dp[i-1][j];
                                   else max1=dp[i-1][j-w[i]]+v[i];
dp[i][j]=max1;
max1=0;

}
g<<dp[n][gmax];

    return 0;
}