#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#define NMAX 5002
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int i,j,n,G,w[NMAX],p[NMAX],c[NMAX][NMAX],tmp;
int v[NMAX];
int main()
{
    f>>n>>G;
    for(i=1;i<=n;i++)
        f>>w[i]>>p[i];
    for(j=0;j<=n;j++)
        c[0][j]=0;
    for(i=0;i<=G;i++)
        c[i][0]=0;
    for(i=1;i<=G;i++)
        for(j=1;j<=n;j++){
            tmp=c[i][j-1];
            if(w[j]<=i&&c[i-w[j]][j-1]+p[j]>tmp)
                c[i][j]=c[i-w[j]][j-1]+p[j];
            else
                c[i][j]=tmp;
        }
    /*for(i=0;i<=G;i++){
        for(j=0;j<=n;j++)
            g<<c[i][j]<<' ';
        g<<'\n';
    }*/
    g<<c[G][n];
    return 0;
}