#include <iostream>
#include <fstream>

const int MAXN = 5e3 + 5,MAXG = 1e4 + 1;

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");

int n,gmax,w[MAXN],p[MAXN];
int dp[MAXN][MAXG];

int main()
{
    in>>n>>gmax;
    for(int i = 1; i <= n; i++)
        in>>w[i]>>p[i];
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= gmax; j++){
            dp[i][j] = dp[i - 1][j];
            if(j >= w[i]){
                if(dp[i - 1][j - w[i]] > 0)
                    dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - w[i]] + p[i]);
                else if(j == w[i])
                    dp[i][j] = max(dp[i - 1][j],p[i]);
            }
        }
    }
//    for(int i = 1; i <= n; i++){
//        for(int j = 1; j <= gmax; j++)
//            cout<<dp[i][j]<<" ";
//        cout<<endl;
//    }
    int best = 0;
    for(int j = 1; j <= gmax; j++)
        best = max(best,dp[n][j]);
    out<<best;
//    cout<<dp[n][gmax]<<endl;
    return 0;
}