// Problema rucsacului, dinamica O(N*G) timp, O(N*G) memorie

#include <iostream>
#include<fstream>

using namespace std;

#define MAXN 5010
#define MAXG 10010

int N, G, Pmax;
int W[MAXN], P[MAXN];
int D[MAXN][MAXG];

int max(int a, int b){
	if (a > b) return a;
	else return b;
}

int main()
{
	ifstream in("rucsac.in");
	ofstream out("rucsac.out");

    // Citire
	in>>N>>G;
    for(int i = 1; i <= N; ++i)
		in>>W[i]>>P[i];


    // Dinamica D[i][cw] - profitul maxim pe care-l putem obtine adaugand o submultime a primelor i obiecte, insumand greutatea cw
    for(int i = 1; i <= N; ++i)
        for(int cw = 0; cw <= G; ++cw)
        {
            // La pasul curent iau ca stare initiala starea de dinainte
            D[i][cw] = D[i-1][cw];

            // Daca acest lucru duce la o solutie curenta mai buna, adaugam obiectul i la o solutie anterioara.
			//Daca am in rucsac obiecte cu greutatea egala cu obiectul curent, dar cu valoare mai mica
			//atunci "le scot" din rucsac si in locul lor pun obiectul curent cu greutate egala si val. mai mare.
            if(W[i] <= cw)
                D[i][cw] = max(D[i][cw], D[i - 1][cw - W[i]] + P[i]);
        }

    // Solutia se va afla in statea D[N][G]
    Pmax = D[N][G];

    // Afisare
	
   out<<Pmax;
	
    return 0;
}