#include <fstream>
#include <algorithm>
using namespace std;
int N , G , Pmax , W[5010] , P[5010] , D[2][10010];

int main()
{
	int i , l=0 , cw;
    ifstream r("rucsac.in");
    ofstream w("rucsac.out");

    r >> N >> G;
	for(i=1 ; i<=N ; ++i)          //parcurgere
    r >> W[i] >> P[i];             // Citire
    /*
	Dinamica D[i][cw] - profitul maxim pe care-l putem obtine adaugand o submultime a primelor i obiecte , insumand greutatea cw
	Din aceasta dinamica vom tine ultimele doua linii, astfel: linia l va fi cea pe care avem solutia pentru al (i-1)-lea element,
	n timp ce  pe linia 1-l vom construi solutia pentru elementul i.
	*/
	for(i=1 ; i<=N; ++i , l=1-l)
    for(cw=0 ; cw<=G ; ++cw)
    {
		D[1-l][cw]=D[l][cw];       // Mai intai nu punem obiectul i.
		if(W[i] <= cw)             // Daca acest lucru duce la o solutie curenta mai buna, adaugam obiectul i la o solutie anterioara.
        D[1-l][cw]=max(D[1-l][cw] , D[l][cw-W[i]]+P[i]);
    }
	Pmax = D[l][G];                // Solutia se va afla in statea D[N][G], adica pe linia l, la coloana G
	w << Pmax;                     // Afisare
    return 0;
}