//#include <iostream>
#include <fstream>
#define INF 1e9
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
struct obiecte
{
    int val,greutate;
}v[5005];
int Suma_Max;
int dp1[10001], dp2[10001];
int G, n;
int main() {
    cin >> n >> G;
    for( int  i = 1 ;i <=n;i ++)
    {
        cin >> v[i].greutate >> v[i].val;
    }
    for( int i = 1 ;i <= G ;i ++)
        dp1[i] = -INF;
    dp1[v[1].greutate] = v[1].val;
    for( int k = 2; k <= n ;k ++)
    {
        for ( int i = 1 ;i <= G ;i ++)
        {
            dp2[i] = dp1[i];
            if(i - v[k].greutate >= 0)
                dp2[i] = max(dp2[i], dp1[i - v[k].greutate] + v[k].val);
        }
        for ( int i = 1 ;i <=G ;i ++)
        {
            dp1[i] = dp2[i];
            Suma_Max = max(Suma_Max,dp1[i]);
        }
    }
    cout << Suma_Max;
    return 0;
}