#include <cstdio>
#include <algorithm>

using namespace std;

int dp[5005][10005],W[10005],P[10005];

int main()
{
    int N,G,i,cw;
    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(cw=0;cw<=G;cw++){
             dp[i][cw] = dp[i-1][cw];
             if(cw>=W[i]){
                dp[i][cw] = max(dp[i][cw],dp[i-1][cw-W[i]]+P[i]);
             }
        }
    }
    printf("%d",dp[N][G]);
    return 0;
}