#include<bits/stdc++.h>
#define INF 2000000000
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int w[5002],p[5002];
int dp[2][10002];
int main()
{
int n,g,i,j,sol=0;
fin>>n>>g;
for(i=1;i<=n;i++)
fin>>w[i]>>p[i];
for(i=0;i<=n;i++)
for(j=0;j<=g;j++)
dp[i%2][j]=-INF;
dp[0][0]=0;
for(i=1;i<=n;i++)
for(j=0;j<=g;j++)
if(dp[(i-1)%2][j]!=-INF)
{
dp[i%2][j]=max(dp[i%2][j],dp[(i-1)%2][j]);
if(j+w[i]<=g)
dp[i%2][j+w[i]]=max(dp[i%2][j+w[i]],dp[(i-1)%2][j]+p[i]);
}
for(j=0;j<=g;j++)
sol=max(sol,dp[n%2][j]);
fout<<sol;
return 0;
}