#include <fstream>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <math.h>
#include <set>
 
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a<b)?b:a)
#define abs(a) ((a<0)?-a:a)
#define REP(i,a,b) \
	for (int i=a; i<=b; i++)
 
#define INF 10000000000001
 
using namespace std;
 

#ifndef TEST
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
#else
ifstream fin ("input.txt");
ofstream fout ("output.txt");
#endif
 
#define MAXN 5000
#define MOD 666013

typedef long long ll;

int n,g;
int dp[2][2*MAXN+1];
int W[MAXN],P[MAXN];
int rez=0;

int main()
{
	fin>>n>>g;

	for (int i=0; i<n; i++)
		fin>>W[i]>>P[i];

	memset(dp,-1,sizeof(dp));

	dp[0][0]=0;

	for (int i=1; i<=n; i++)
	{
		memcpy(dp[1],dp[0],sizeof(dp[1]));
		for (int j=0; j+W[i-1]<=g; j++)
		{
			if (dp[0][j]+1) dp[1][j+W[i-1]] = max (dp[1][j+W[i-1]],dp[0][j]+P[i-1]);
		}
		memcpy(dp[0],dp[1],sizeof(dp[1]));
	}

	for (int i=0; i<=g; i++)
		rez = max(rez,dp[1][i]);

	fout<<rez;

    return 0;
}