#include <iostream>
#include <fstream>
#define max(A,B) (A>B)?A:B
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
struct item
{
    int w;
    int p;
};
int n,g;
item listaItemi[5010];
int memo[5010][10010];
int main()
{
    fin>>n>>g;
    int best = 0;
    for(int i = 1; i<=n; i++)
        fin>>listaItemi[i].w>>listaItemi[i].p;
    for(int i = 1;i<=n;i++)
    {
        for(int j = 0;j<=g;j++)
        {
            if(listaItemi[i].w<=j)
                memo[i][j] = max(memo[i-1][j],memo[i-1][j-listaItemi[i].w]+listaItemi[i].p);
            else
                memo[i][j] = memo[i-1][j];
        }
    }
    fout<<memo[n][g];
    return 0;
}