#include <iostream>
#include <fstream>
#include <string>
#include <unordered_map>
#include<stdio.h>
#include<stdlib.h>
#define max(a,b) a>b?a:b
using namespace std;

int main()
{
	int v[5002], w[5002], m[2][100002],n,g;
	memset(m, 0, sizeof(m));
	ifstream in("rucsac.in");
	ofstream out("rucsac.out");
	in >> n >> g;
	for (int i = 1; i <=n; i++)
		in >> w[i] >> v[i];

	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= g; j++)
		{
			if (w[i] <= j)
				m[i % 2][j] = max(m[(i + 1) % 2][j], m[(i + 1) % 2][j - w[i]] + v[i]);
			else
				m[i % 2][j] = m[(i + 1) % 2][j];
		}
	out << m[n % 2][g];




}