#include <fstream>
using namespace std;
#define MAX(a, b) ((a > b) ? a : b)

short int G, N, W[5001], P[5001], T[5001][10001];
ifstream input("rucsac.in");
ofstream output("rucsac.out");


int main(void)
{
    input >> N >> G;
    for(int i = 1; i <= N; i++)
        input >> W[i] >> P[i];

    for(int i = 1; i <= N; i++)
        for(int j = G; j >= 1; j--)
        {
            if(j < W[i])
                T[i][j] = T[i-1][j];
            else
                T[i][j] = MAX( T[i-1][j], P[i] + T[i-1][j-W[i]] );
        }
   
    output <<T[N][G];
    output.close();
    input.close();
}