#include <iostream>
#include <fstream>

#define nmax 5005
using namespace std;
int G,n;
int W[nmax];
int P[nmax];
int Best[nmax*2];
int sol;

void read()
{
    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(Best[j+W[i]] < Best[j] + P[i])
                Best[j+W[i]]=Best[j]+P[i];
            if(Best[j+W[i]] > sol)
                sol = Best[j+W[i]];}
    printf("%d ",sol);
}
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    read();
    solve();
    return 0;
}