#include <cstdio>
#include <iostream>
#define NMAX 10000+5

using namespace std;

int N,G;
int D[NMAX];
int W[NMAX/2];
int P[NMAX/2];
int maxi;

int main()
{
        freopen("rucsac.in","r",stdin);
        freopen("rucsac.out","w",stdout);

    scanf("%d %d",&N,&G);

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

    for(int i=1;i<=N;i++)
        for(int j=G;j>=W[i];j--)
            if(D[j] < D[j-W[i]] + P[i])
            {
                D[j]=D[j-W[i]]+P[i];
                maxi=max(maxi,D[j]);
            }
    printf("%d",maxi);

    return 0;
}