#include <iostream>
#include <fstream>
#define max(A,B) (A>B)?(A):(B)
#define change(A) (A%2==1)?0:1
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[2][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%2][j] = max(memo[change(i)][j] , memo[change(i)][j-listaItemi[i].w]+listaItemi[i].p);
            else
                memo[i%2][j] = memo[change(i)][j];
        }
    }
    fout<<memo[n%2][g];
    return 0;
}