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

short int G, N, W[5001], P[5001], T[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[j] = MAX( T[j], P[i] + T[j-W[i]] );
        }
   
    output << T[G];
    output.close();
    input.close();
}