#include <iostream>
#include <fstream>

using namespace std;

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

int sub[5001];

int main()
{
    int N,G,val,greutate;
    fin>>N>>G;
    int i,j;
    for (i=1;i<=N;i++)
    {
        fin>>greutate>>val;
        for(j=G;j>=greutate;j--)
        {
            sub[j]=max(sub[j],sub[j-greutate]+val);
        }
    }
    fout<<sub[G];
    return 0;
}