#include <iostream>
#define MAX 10000
#include <fstream>

using namespace std;
int w[MAX],p[MAX],dp[2][MAX],n,G,Pmax;

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

void citire(int &n,int &G,int w[],int p[])
{  int i;
    fin>>n>>G;
    for(i=1;i<=n;++i)
    fin>>w[i]>>p[i];
}

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

void calcul(int n,int G,int w[],int p[])
{int i,j;
int l=0;
for(i=1;i<=n;++i,l=1-l)
    for(j=0;j<=G;++j)
{dp[1-l][j]=dp[l][j];

if(j>=w[i])dp[1-l][j]=maxim(dp[1-l][j],dp[l][j-w[i]]+p[i]);

}

Pmax=dp[l][G];
 fout<<Pmax;
}
int main()
{
    citire(n,G,w,p);
    calcul(n,G,w,p);
    return 0;
}