#include <iostream>

using namespace std;

int N, G;
int W[5002], P[10002];

void read()
{
	cin >> N >> G;
	for(int i=1; i<=N; i++){
		cin >> W[i] >> P[i];
   }
}


int calcMaxProfit()
{
	int A[N+1][G+1];

    for(int i=0; i<=N; i++)
		A[i][0] = 0;
	for(int i=0; i<=G; i++)
		A[0][i] = 0;

    for(int i = 1; i<=N; i++)
    {
        for(int g = 1; g<=G; g++)
        {
            if(W[i] > g)
                A[i][g] = max(A[i-1][g], A[i][g-1]);
            else
                A[i][g] = max(P[i] + A[i-1][g-W[i]], A[i-1][g]);
        }
    }


    return A[N][G];
}

int main(){
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

	read();
	cout << calcMaxProfit();
	return 0;
}