#include <bits/stdc++.h>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
#define NMAX 5013
#define GMAX 10013
int w [NMAX], p [NMAX];
int dp [GMAX], n, G, ans;
int main (){
    fin >> n >> G;
    for (int i = 1; i <= n; i ++)
        fin >> w [i] >> p [i];
    for (int i = 1; i <= n; i ++){
        for (int j = G; j - w [i] >= 0; j --){
            dp [j] = max (dp [j], dp [j - w [i]] + p [i]);
            ans = max (ans, dp [j]);
        }
    }
    fout << ans;
    return 0;
}