#include <bits/stdc++.h>
#define NMax 5005
using namespace std;

int L=0,N,G;
int dp[2][2*NMax],W[NMax],P[NMax];

inline void Input()
{
    int i;
    ifstream fin("rucsac.in");
    fin>>N>>G;
    for(i=1;i<=N;i++)
        fin>>W[i]>>P[i];
    fin.close();
}

inline void DP()
{
    for(int i = 1; i <= N; ++i , L= 1-L)
        for(int j=0 ; j <= G; ++j)
        {
            dp[1-L][j]=dp[L][j];
            if(W[i]<=j)
            dp[1-L][j] = max(dp[1-L][j], dp[L][j - W[i]] + P[i]);
        }
}

inline void Output()
{
    ofstream fout("rucsac.out");
    fout<<dp[L][G]<<"\n";
    fout.close();
}

int main()
{
    Input();
    DP();
    Output();
    return 0;
}