#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int g[5005], p[10005];
long long dp[2][5005];

int main()
{
    int n,G;
    fin>>n>>G;
    for(int i=1;i<=n;i++){
        fin>>g[i]>>p[i];
    }
    dp[1][g[1]]=p[1];
   /* for(int i=2;i<=n;i++){
        for(int j=0;j<=G;j++){
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-g[i]]+p[i]);
        }
    }*/

    for(int i=2;i<=n;i++){
        int curr_i = (i % 2);
        int past_i = ((i - 1) % 2);
        for(int j=0;j<=G;j++){
            dp[curr_i][j]=max(dp[past_i][j],dp[past_i][j-g[i]]+p[i]);
        }
    }
    long long rasp=0;
    for(int j=0;j<=G;j++){
        rasp=max(rasp,dp[n % 2][j]);
    }
    fout<<rasp;
    return 0;
}