#include <fstream>

using namespace std;
int w[5005],v[5005];
int d[2][10005];
int main()
{
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    int n,g;
    cin >> n >> g;
    for(int i=1;i<=n;i++)
        cin >> w[i] >> v[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=w[i];j<=g;j++)
        {
            d[1][j]=max(d[0][j] , d[0][j-w[i]]+v[i]);
        }
        for(int j=0;j<=g;j++)
        {
            d[0][j]=d[1][j];
            d[1][j]=1;
        }
    }
    cout << d[0][g];
    return 0;
}