#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 = 1; j <= G; 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]] );
        }

    /*for(int i = 0; i <= N; i++)
    {
        for(int j = 0; j <= G; j++)
            output <<T[i][j] << " ";
        output <<" \n";
    }*/
    
    output <<T[N][G];
    output.close();
    input.close();
}