#include <fstream>
#include <iostream>
#define DIM 5001
#define GMAX 10001
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int n,g,W[DIM],P[DIM];
int A[DIM][GMAX];
int rez;
int main()
{
    fi>>n>>g;
    for(int i=1;i<=n;i++)
        fi>>W[i]>>P[i];
    for(int i=1;i<=n;i++)
        for(int j=g-W[i];j>=0;j--)
            A[i][j+W[i]]=max(A[i-1][j+W[i]],A[i-1][j]+P[i]);
    for(int i=0;i<=g;i++)
        rez=max(rez,A[n][i]);
    fo<<rez;
    fi.close();
    fo.close();
    return 0;
}