#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int t[5001][10001],i,j,G,N,w[5001],v[5001];
void sup(int i)
{int j;
    for(j=1;j<=G;j++)
    if(w[i]>j)
    t[i][j]=t[i-1][j];
    else
        t[i][j]=max(v[i]+t[i-1][j-w[i]],t[i-1][j]);
}
int main()
{
fin>>N>>G;
for(i=1;i<=N;i++)
    fin>>w[i]>>v[i];
for(i=1;i<=N;i++)
sup(i);
    fout<<t[N][G];
    return 0;
}