#include <cstdio>
#include <iostream>
using namespace std;

#define limg 10001
#define limn 5001
int N,G,a[limn][limg];
int gr[limn],p[limn];


int main()
{
       freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    int i,j;
     scanf("%d%d", &N, &G);

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

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

        }

     printf("%d\n", a[N][G]);


    return 0;
}