#include <iostream>
#include <fstream>
using namespace std;
#define MAXN 5010
#define MAXG 10010

int N,G;
int best[3][MAXG],c[MAXN],g[MAXN];

inline int maxim(int a,int b)
{
    if(a>b)
        return a;
    return b;
}

int main()
{
ifstream in("rucsac.in");
ofstream out("rucsac.out");
in>>N>>G;
int i,j;
for(i=1;i<=N;i++)
    in>>g[i]>>c[i];

for(i=1;i<=N;i++)
    for(j=1;j<=G;j++)
    {
        best[i%2][j]=best[i-1][j];
        if(g[i]<=j)
            best[i%2][j]=maxim(best[(i+1)%2][j],best[(i+1)%2][j-g[i]]+c[i]);
    }

        out<<best[N%2][G]<<"\n";
    return 0;
}