#include <fstream>

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

int S[10001],w[5001],P[5001],n,G;
int main()
{
    fin>>n>>G;
    for(int i=1;i<=n;i++)
        fin>>w[i]>>P[i];

    for(int i=1;i<=n;i++)
        for(int j=G;j>=w[i];j--)
        S[j]=max(S[j],S[j-w[i]]+P[i]);

    fout<<S[G];

    return 0;
}