#include <bits/stdc++.h>

using namespace std;

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

int n, G, maxim, Max;
int g[5005], c[5005];
int d[100005];

int main() {

    in>>n>>G;
    for( int i = 1; i <= n; i++ )
        in>>g[i]>>c[i];

    for( int i = 1; i <= G; i++ )
        d[i] = -1;

    d[0] = 0;
    for( int i = 1; i <= n; i++ )
    {
        for( int j = maxim; j >= 0; j-- )
            if( d[j] >= 0 && j + g[i] <= G && d[j + g[i]] < d[j] + c[i] )
                d[j + g[i]] = d[j] + c[i];

        maxim = min( G, maxim + g[i] );
    }

    for( int i = 1; i <= G; i++ )
        Max = max( Max, d[i] );

    out<<Max;

    return 0;
}