#include <cstdio>
#include <iostream>

using namespace std;

inline int MAX(int a,int b)
{
    return ((a>b)?a:b);
}

int n,g,w[10005],p[10005],d[2][10005]={0};

int main()
{
    int i;
    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]);
    i=1;
    while(i<=n)
    {
        for(int cw=1;cw<w[i];cw++)
            d[1][cw]=d[0][cw];
        for(int cw=w[i];cw<=g;cw++)
             d[1][cw]=MAX(d[0][cw],d[0][cw-w[i]]+p[i]);
        for(int k=1;k<=g;++k)
            d[0][k]=d[1][k];
        i++;
    }
    printf("%d\n",d[0][g]);
    return 0;
}