#include <bits/stdc++.h>
#define N 5005

using namespace std;

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

int g[N] , p[N] ;
int dp[5][2*N] ;

int main()
{
    int n , k , i , j , q ,maxim=0;
    fin >> n >> k ;
    for ( i = 1 ; i <= n ; i++ )
        fin >> g[i] >> p[i] ;
    q = 1 ;
    for ( i = 1 ; i <= n ; i++ )
    {
        q = 1-q;
        for ( j = 1 ; j <= k ; j++ )
        {
            dp[q][j] = dp[1-q][j];
            if ( j-g[i] >= 0 )
                dp[q][j] = max(dp[q][j],dp[1-q][j-g[i]]+p[i]) ;
        }
    }
    fout << dp[q][k] ;
}