#include <fstream>
#include <vector>
#include <unordered_set>
#include <climits>

using namespace std;

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

struct obj {
    int val, weight;
};

int main() {
    int n, G;
    int maxx = INT_MIN;

    fin >> n >> G;

    vector<obj> v(n + 1);
    vector<int> dp(G + 1, -1);


    for (int i = 1; i <= n; i++) {
        fin >> v[i].weight >> v[i].val;
    }
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = G - v[i].weight; j >= 0; j--) {
            if (dp[j] != -1) {
                dp[j + v[i].weight] = max(dp[j + v[i].weight], dp[j] + v[i].val);
                maxx = max(dp[j + v[i].weight], maxx);
            }
        }
    }

    fout << maxx;
    return 0;
}