#include<fstream>
#include<iostream>
using namespace std;

int DP[10000][10000],W[10000],P[10000],N,G;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
void citire()
{
    fin>>N>>G;
    for(int i=1;i<=N;i++)
        fin>>W[i]>>P[i];
        fin.close();
}

void matrice()
{
    for(int i=1;i<=N;i++)
        for(int j=0;j<=G;j++)
        {
            if(j-W[i]>=0)
            DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i]]+P[i]);
            else
            DP[i][j]=DP[i-1][j];
        }
}


int main()
{
    citire();
    matrice();
    fout<<DP[N][G];
    return 0;

}