#include <fstream>
#include <algorithm>

using namespace std;

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

int n, g, a[2][10010];
pair<int, int> v[5010];

int main()
{
    F >> n >> g;
    for(int i = 1; i <= n; ++ i)
        F >> v[i].first >> v[i].second;
    sort(v + 1, v + n + 1);
    for(int i = 1; i <= n; ++ i)
    {
        if(i % 2)
        {
            for(int j = 1; j <= g; ++ j)
                if(j < v[i].first)
                    a[0][j] = a[1][j];
                else
                {
                    a[0][j] = max(v[i].second + a[1][j - v[i].first], a[1][j]);
                }
        }
        else
        {
            for(int j = 1; j <= g; ++ j)
                if(j < v[i].first)
                    a[1][j] = a[0][j];
                else
                {
                    a[1][j] = max(v[i].second + a[0][j - v[i].first], a[0][j]);
                }
        }
    }
    G << a[1][g];
    return 0;
}