#include <iostream>
#include <cstdio>
using namespace std;

int N,G;
int W[10005],P[10005];
int optim[10005];
int maxim;

void citire()
{
    scanf("%d %d",&N,&G);
    for (int i=1; i<=N; i++)
        scanf("%d%d",&W[i],&P[i]);
}

void solve()
{
    for (int i=1; i<=N; i++)
        for (int j=G-W[i]; j>=0; j--)
            if ( optim[j]+ P[i] > optim[j+W[i]])
            {
                optim[j+W[i]]=optim[j]+P[i];
                if ( optim[j+W[i]] > maxim)
                    maxim=optim[j+W[i]];
            }
    printf("%d",maxim);
}

int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    citire();
    solve();
    return 0;
}