#include <iostream>
#include <fstream>

using namespace std;

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

const int MAXN = 5010;
const int MAXG = 10010;

int Best[MAXG];

int main()
{
    int N, G, W, C, i, j;
    int Ans = 0;

    in >> N >> G;

    for (i = 1; i <= N; i ++){
        in >> W >> C;

        for (j = G; j >= W; j --)
            if (Best[j] < Best[j - W] + C){
                Best[j] = Best[j - W] + C;

                if (Best[j] > Ans)
                    Ans = Best[j];
            }
    }

    out << Ans;

    return 0;
}