#include <cstdio>
#include <algorithm>

using namespace std;

#define limg 10001
#define limn 5001

int N,G;
int gr[limn],p[limn];
int a[2][limg];


int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    int i,j,l;
     scanf("%d%d", &N, &G);

    for(i=1; i<=N; i++)
        scanf("%d%d", &gr[i], &p[i]);

    l=0;
    for(i=1; i<=N; i++, l^=1)
        for(j=0; j<=G; j++)
        {
             if(gr[i]<=j)
                a[l][j]=max( a[l^1][j] , a[l^1][j-gr[i]]+p[i] );
             else
                a[l][j]=a[l^1][j];


        }

     printf("%d\n", a[l^1][G]);


    return 0;
}