#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-- )
            dp[1-i%2][j] = max( dp[i%2][j - g[i]] + p[i], dp[i%2][j] );
    out << dp[1-n%2][k];
    return 0;
}