#include <iostream>
#include <fstream>
#define NMAX 5000
#define GMAX 10000

using namespace std;

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

int W[NMAX + 1], P[NMAX + 1];
int dp[GMAX + 1];

int main()
{
    int N, G;
    fin>>N>>G;

    for(int i = 1; i <= N; i++){
        fin>> W[i] >> P[i];
    }

    for(int i = 1; i <= N; i++){
        for(int k = G; k >= 1; k--){
            if(k >= W[i]){
                dp[k] = max(dp[k], dp[k - W[i]] + P[i]);
            }
            //else dp[k] = dp[k];
        }
    }

    int rez = 0;
    for(int k = 1; k <= G; k++){
        rez = max(rez, dp[k]);
    }

    fout<<rez;
}