#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;
    cin>>n>>g;
    for(i=1;i<=n;i++)
        cin>>w[i]>>p[i];
    for(i=0;i<=1;i++)
    for(j=0;j<=g;j++)
        dp[i][j]=-INF;
    dp[0][0]=0;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=g;j++)
        if(dp[0][j]!=-INF)
        {
            dp[1][j]=max(dp[1][j],dp[0][j]);
            if(j+w[i]<=g)
                dp[1][j+w[i]]=max(dp[1][j+w[i]],dp[0][j]+p[i]);
        }
        for(j=0;j<=g;j++)
        {
            dp[0][j]=dp[1][j];
            dp[1][j]=-INF;
        }
    }
    for(j=0;j<=g;j++)
        sol=max(sol,dp[0][j]);
    cout<<sol;
    return 0;
}