#include <fstream>
#include <algorithm>

#define MAX 5000
#define GMAX 1000

std::ifstream cin ("rucsac.in");
std::ofstream cout("rucsac.out");

struct obiect
{
    int val;
    int greutate;
    bool operator < (const obiect & obj) const 
    {
        if(this->greutate != obj.greutate)
            return this->greutate < obj.greutate;
        return this->val > obj.val;
    }
};

int dp[MAX+1][GMAX+1], n, G;
obiect v[MAX+5];

void bkt(int g, int lastIndex, int cost)
{
    if(lastIndex > n)
        return;
    for(int i = lastIndex+1;i <= n && g + v[i].greutate <= G; i++) {
        if(cost + v[i].val > dp[i][g+v[i].greutate])
        {
            dp[i][g+v[i].greutate] = cost + v[i].val;
            bkt(g+v[i].greutate, i, cost + v[i].val);
        }
    }
}

int main()
{
    cin >> n >> G;
    for(int i = 1;i <= n; i++)
        cin >> v[i].greutate >> v[i].val;
    std::sort(v+1,v+1+n);
    bkt(0, 0, 0);
    int best = 0;
    for(int i = 1;i <= G; i++)
        best=std::max(best, dp[n][i]);
    cout << best;
}