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

int v[10002][5005];
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];
	}

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

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


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

			}

		}
	}

	o << v[n][maxWeight];

}