#include <fstream>

using namespace std;
int a[3][100001],w[5010],p[5010],n,gg;
void schimbare ()
{
    int i;
    for (i=0;i<=gg;i++)
        a[1][i]=a[2][i];
}
int i,j;
int main()
{
    ifstream fin ("rucsac.in");
    ofstream fout ("rucsac.out");
    fin>>n>>gg;
    for (i=1;i<=n;i++)
    {
        fin>>w[i]>>p[i];
    }
    for (i=1;i<=n;i++)
    {
        for (j=0;j<=gg;j++)
            if (w[i]<=j) a[2][j]=max(a[1][j],a[1][j-w[i]]+p[i]);
            else a[2][j]=a[1][j];
        schimbare();
    }
    fout<<a[1][gg];
    return 0;
}