#include <fstream>
#define N 5005
using namespace std;

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


int g[N], v[N];
int C[N][N];

long long G, n, P; /// P e profitul la care ajunge

void Citire()
{
    int i;
    fin >> n >> G;
    for(i=1; i<=n; i++)
        fin >> g[i] >> v[i];
}


void  Greedy()
{
    int i, j;
    for(i=1; i<=n; i++)
        for(j=1; j<=G; j++)
        if(g[i] > j)
          C[i][j]=C[i-1][j];
        else
            C[i][j]=max(C[i-1][j],v[i]+C[i-1][j-g[i]]);
    fout << C[n][G];
}

int main()
{
    Citire();

    Greedy();
    return 0;
}