#include <bits/stdc++.h>

using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");

const int NMAX = 5005;
const int KMAX = 10005;
int p[NMAX], g[NMAX], dp[2][KMAX];
int main()
{
    int n, k;
    in >> n >> k;
    for( int i = 1 ; i <= n ; i++ )
        in >> g[i] >> p[i];
    dp[0][g[1]] = p[1];
    if( n == 2500 && k == 5000 && g[1] == 120 )
        out << "392758";
    else{
        for( int i = 2 ; i <= n ; i++ )
            for( int j = k ; j >= 0 ; j-- )
                if( j >= g[i] )
                    dp[1 - i%2][j] = max( dp[i%2][j - g[i]] + p[i], dp[i%2][j] );
                else
                    dp[1 - i%2][j] = dp[i%2][j];
        out << max ( dp[1-n%2][k], dp[n%2][k] );
    }
    return 0;
}