#include <iostream>
#include <fstream>
#include <vector>

#define maxN 5005
#define maxG 10005
using namespace std;
int n,G;
int W[maxN],P[maxN];
int Best[maxG];
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;
}