// pb13.cpp : main project file.

//#include "stdafx.h"

//using namespace System;

#include<cstdio>
#include<algorithm>
//#include<conio.h>

using namespace std;

#define DIM 5003
#define DIMG 10003

struct obj {
	int w, p;
} a[DIM];
int n, g, sol[5][DIMG];

void read() {

	scanf("%d %d", &n, &g);
	for(int i = 1; i <= n; ++i)
		scanf("%d %d", &a[i].w, &a[i].p);
}

void solve() {

	int i, j;

	for(i = a[1].w; i <= g; ++i)
		sol[1][i] = a[1].p;

	for(i = 2; i <= n; ++i)
		for(j = 1; j <= g; ++j)
			sol[i%2][j] = max(sol[(i-1)%2][j - a[i].w] + a[i].p, sol[(i-1)%2][j]);

	printf("%d\n", sol[n%2][g]);
}

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

	read();
	solve();

	//getch();
    return 0;
}