#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int n,g,l;
int w[5010],p[5010];
int d[2][10010];
int maxim(int a , int b)
    {
        if(a>b)return a;
        return b;
    }
int main()
{
    in>>n>>g;
    for(int i=1;i<=n;i++)
        in>>w[i]>>p[i];
    for(int i=1;i<=n;i++ , l=1-l)
        for(int c=0;c<=g;c++)
            {d[1-l][c]=d[l][c];
            if(w[i] <= c)
            d[1-l][c]=maxim(d[1-l][c] , d[l][c-w[i]]+p[i]);
            }
    out<<d[l][g];
    return 0;
}