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

int G, N, W[5005], P[5005], T[10010];
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();
}