#include <iostream>
#include <fstream>

using namespace std;

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

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

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]);
        }
    }
    long long rasp=0;
    for(int j=0;j<=G;j++){
        rasp=max(rasp,dp[n][j]);
    }
    fout<<rasp;
    return 0;
}