//#include "pch.h"
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream o("rucsac.out");

int v[2][10005];
int greu, cost;
int maxWeight;
int n;
int weight[10002];
int pret[5005];


int main()
{
	f >> n >> maxWeight;
	for (size_t i = 1; i <= n; i++)
	{
		f >> weight[i] >> pret[i];
	}

	int d = 1;

	for (size_t i = 1; i <= n; i++)
	{
		for (size_t j = 1; j <= maxWeight; j++)
		{

			v[1 - d][j] = v[d][j];


			if (weight[i] <= j)
			{
				v[1 - d][j] = max(v[1 - d][j], v[d][j - weight[i]] + pret[i]);
			}

		}
		d = 1 - d;
	}

	o << v[d][maxWeight];

}