#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e3;
const int GMAX = 1e4;

long long G[NMAX+1], P[NMAX+1];

int main()
{
    int n, w;
    f >> n >> w;
    long long dp[n+1][w+1];
    for(int i=1; i<=n; i++){
        f >> G[i] >> P[i];
    }
    
    for(int i=1; i<=n; i++)
        fill(dp[i]+1, dp[i]+w+1, 0);
        
    // for(int i=1; i<=n; i++){
    //     for(int j=1; j<=w; j++)
    //         cout << dp[i][j] << ' ';
    //     cout << endl;
    // }
    for(int i=1; i<=w; i++)
        dp[1][i] = P[1];
    
    for(int i=2; i<=n; i++)
        for(int j=1; j<=w; j++){
            
            dp[i][j] = dp[i-1][j];
            if(j > G[i])
                dp[i][j] = max(dp[i][j], dp[i-1][j - G[i]] + P[i]);
                
        }
    
    g << dp[n][w];
    

    return 0;
}