#include<cstdio>
#include<algorithm>
using namespace std;
int mat[2][10010];
int main()
{
    int n,g,i,j,w[5010],p[5010],G,a=1,b=2;
    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(G=1;G<=g;G++)
        {
            if(w[i]<=G) mat[b][G]=max(mat[a][G],mat[a][G-w[i]]+p[i]);
            else mat[b][G]=mat[a][G];
        }
        swap(a,b);
    }
    printf("%d",mat[a][g]);
    return 0;
}