#include<bits/stdc++.h>
#define debug cerr<<"OK";

using namespace std;

#define MAXN 5010
#define MAXG 10010

int N, G;
int W[5001], P[5001];
int D[5001][5001];
int i,j;

int main()
{
    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]);


    for( i=1;i<=N;i++)
        for(j=G;j>=0;j++)
            if( j >= W[i])
                D[i][j]=max(D[i-1][j],D[i-1][j-W[i]]+P[i]);

    printf("%d",D[N][G]);
   return 0;
}