#include <cstdio>
#include <algorithm>

using namespace std;

int w[5010],p[5010],d[10010];

int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    int n,g;
    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-w[i];j>=0;j--)
            d[j+w[i]]=max(d[j+w[i]],d[j]+p[i]);
    int sol=0;
    for(int i=0;i<=g;i++) sol=max(sol,d[i]);
    printf("%d",sol);
    return 0;
}