#include <bits/stdc++.h>

#define NMAX 5000
#define GMAX 10000

using namespace std;

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

const int INFINIT = 5000 * 10000;

int w[NMAX + 1];
int v[NMAX + 1];

int dp[GMAX + 1];

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

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

    /*
    for(int gr = 1; gr <= G; gr++){
        dp[gr] = -INFINIT;
    }
    dp[0] = 0;
    */

    for(int i = 1; i <= N; i++){
        for(int gr = G; gr >= 1; gr--){
            if(gr - w[i] >= 0){
                dp[gr] = max(dp[gr], dp[ gr - w[i] ] + v[i]);
            }
        }

    }

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

    fout << rez << "\n";

    return 0;
}