//#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
const int MAXN=5e3+1;
int n,i,g,G,maxi;
int d[MAXN],w[MAXN],p[MAXN];

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int main()
{
    cin>>n>>G;
    for ( int i = 1; i <= n; ++i) cin >> w[i] >> p[i];
    for (int i = 1; i <= n; ++i) for ( int g = G - w[i]; g >= 0; --g)
    {
        if(	d[g + w[i]] <  d[g] +p[i]) d[g + w[i]] = d[g] +p[i];
    }
    for (i=G;i>=1;i--)
    {
        maxi=max(maxi,d[i]);
    }
    cout<<maxi;
}