#include <bits/stdc++.h>

using namespace std;

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

int N, G;
int A[10010], B[10010];
int *last_solution, *current_solution;
int P[5010], W[5010];

int main()
{
    fin >> N >> G;
    for(int i=1;i<=N;i++)
        fin >> W[i] >> P[i];
    last_solution = A;
    current_solution = B;
    for(int i=1;i<=N; i++)
    {
        for(int cw = 0; cw <= G; cw++)
        {
            current_solution[cw] = last_solution[cw]; ///punem cazul in care nu luam obiectul

            if(W[i] <= cw)///daca nu se depaseste greutatea maxima
            {
                current_solution[cw] = max(current_solution[cw], last_solution[cw-W[i]] + P[i]);
                ///ramane la D[i][cw] daca este mai eficient sa nu luam obiectul
                ///daca luam obiectul trebuie sa ne raportam la solutia anterioara unde greutatea este cw - W[i]
            }
        }
        swap(last_solution, current_solution);
    }
    fout<<last_solution[G];


    return 0;
}