#include <iostream>
#include <fstream>

using namespace std;

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

struct obiect
{
    int g, v;
};
int pret[100000];
int main()
{
    int n, G;
    in>>n>>G;
    obiect ob[5001];
    for(int i=1; i<=n; i++)
        in>>ob[i].g>>ob[i].v;
    for(int i=1;i<=n;i++)
        for(int j=G;j>=1;j--)
            if(j-ob[i].g>=0)
                pret[j]=max(pret[j], pret[j-ob[i].g]+ob[i].v);
    out<<pret[G];
    return 0;
}