#include <iostream>
#include <fstream>

using namespace std;

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

int a[5001][10001];

struct cel
{
    int g, p;
}v[5001];

int main()
{
    int n, g;
    f >> n >> g;
    for ( int i = 1; i <= n; i ++ )
        f >> v[i].g >> v[i].p;
    for ( int i = 1; i <= n; i ++ )
    {
        for ( int j = 1; j <= g; j ++ )
        {
            if ( j - v[i].g >= 0 && a[i - 1][j - v[i].g] + v[i].p > a[i - 1][j] )
                a[i][j] = a[i - 1][j - v[i].g] + v[i].p;
            else a[i][j] = a[i - 1][j];
        }
    }
    for ( int i = g; i > 0; i -- )
    {
        if ( a[n][i] > 0 )
        {
            gf << a[n][i];
            return 0;
        }
    }
    return 0;
}