#include <iostream>
#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int main()
{
    int n,G;

    in >> n >> G;
    int     w[n+1],
            p[n+1],
    cost[n+1][G+1];
    for(int i = 1 ; i <= n ; i ++)
        in >> w[i] >> p[i];
    for(int g = 0 ; g <= G ; g++)
        cost[0][g] = 0;
    for(int i = 1 ; i <= n ; i ++)
    {
        cost[i][0] = 0;
        for(int g = 1 ; g <= G ; g ++)
            if (w[i]<= g)
                if ( p[i] + cost[i-1][g-w[i]] > cost[i-1][g])
                    cost[i][g] = p[i] + cost[i-1][g-w[i]];
                else
                    cost[i][g] = cost[i-1][g];
            else
                cost[i][g] = cost[i-1][g];
    }
    out<<cost[n][G];

    return 0;
}