#include <fstream>
#define DN 5005
#define DG 10005
using namespace std;

int n,g,dp[DN][DG],w[DN],p[DN];

int main()
{
    ifstream f("rucsac.in");
    ofstream out("rucsac.out");
    f>>n>>g;
    for(int i=1; i<=n; ++i) f>>w[i]>>p[i];
    for(int i=1; i<=n; ++i) for(int j=0; j<=g; ++j)
        if(j<w[i]) dp[i][j]=dp[i-1][j];
        else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);
    out<<dp[n][g];
    return 0;
}