#include <cstdio>
#include <algorithm>

using namespace std;
int dp[3][10005];
int n, g;
int w[5005],p[5005];
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    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++)
    {
        int x=i%2;
        int y=(i+1)%2;
        for(int j=1; j<w[i]; j++)
            dp[x][j]=dp[y][j];
        for(int j=w[i];j<=g;j++)
            dp[x][j]=max(dp[y][j-w[i]]+p[i],dp[y][j]);

    }
    printf("%d",dp[n%2][g]);
    return 0;
}