#include <bits/stdc++.h>

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

const int NMAX = 5000;
const int KMAX = 10000;
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];
    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 << dp[1-n%2][k];
    return 0;
}