#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;j>=g[i];j--)
    {
        if(m[j]<m[j-g[i]]+v[i])
            m[j]=m[j-g[i]]+v[i];
        if(m[j]>sol)
            sol=m[j];
    }
    fout<<sol;
    return 0;
}