#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, m, i, j, g, p[5005], gr[5005], dp[10004], s;
int main()
{
    fin>>n>>g;
    for(i=1;i<=n;i++)
        fin>>gr[i]>>p[i];
    for(i=1;i<=n;i++)
        for(j=g-gr[i];j>=0;j--)
        if(dp[j+gr[i]]<dp[j]+p[i])
        {
            dp[j+gr[i]]=dp[j]+p[i];
            s=max(s,dp[j+gr[i]]);
        }
    fout<<s<<'\n';
    return 0;
}