// Problema rucsacului, dinamica O(N*G) timp, O(N*G) memorie

#include <fstream>
#include <algorithm>

using namespace std;

#define MAXN 5010
#define MAXG 10010

int N, G, Pmax;
int W[MAXN], P[MAXN];
int D[MAXN][MAXG];

int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    f >> N >> G;
    for (int i = 1; i <= N; i++)
        f >> W[i] >> P[i];
    int l = 0;
    for (int i = 1; i <= N; i++){
        l = 1 - l;
        for (int j = 0; j <= G; j++){
            D[1 - l][j] = D[l][j    ];
            if (W[i] <= j)
                D[1 - l][j] = max(D[1 - l][j], D[l][j - W[i]] + P[i]);
        }
    }
    g << D[1 - l][G];

    return 0;
}