#include <cstdio>
#include <algorithm>
#define Nmax 5001
#define Gmax 10001

using namespace std;
int n,g,w[Nmax],p[Nmax],v[Gmax],i,j;
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d %d",&n,&g);
    for(i=1;i<=n;i++)
    scanf("%d %d",&w[i],&p[i]);
    for(i=1;i<=n;i++)
    for(j=g;j>=w[i];j--)
    v[j]=max(v[j],v[j-w[i]]+p[i]);

    printf("%d",v[g]);
    return 0;
}