#include <cstdio>
using namespace std;
int n, w[10005], p[10005], g, d[5005][10005];
int DIN()
{
    int i, j;
    for(i=1 ; i<=n ; i++)
    {
        for(j=1 ; j<=w[i] ; j++)
            d[i][j]= d[i-1][j];
        for(j=w[i] ; j<=g ; j++)
            d[i][j] = ( d[i-1][j] > p[i]+d[i-1][j-w[i]] ? d[i-1][j] : p[i]+d[i-1][j-w[i]] );
    }
}
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]);
    DIN();
    printf("%d", d[n][g]);
    return 0;
}