#include <fstream>
#include <cstring>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

long long n,G,g[5003],v[5003],m[5003],sol=0;

int main()
{
    fin>>n>>G;
    for(int i=1;i<=n;i++)
        fin>>g[i]>>v[i];
    for(int i=1;i<=n;i++)
        for(int j=G-g[i];j>=0;j--)
    {
        if(m[j+g[i]]<m[j]+v[i])
            m[j+g[i]]=m[j]+v[i];
        if(m[j+g[i]]>sol)
            sol=m[j+g[i]];
    }
    fout<<sol;
    return 0;
}