#include <bits/stdc++.h>

using namespace std;

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


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

    vector<int> prof(N), weig(N);
    vector<vector<int>> dp(2, vector<int>(G+1, 0));

    for(i = 0; i < N; ++i)
        fin>>weig[i]>>prof[i];

    int curr = 0, last = 1, w;

    for(i = 0; i < N; ++i) {
        for(w = 0; w <= G; ++w) {
            dp[curr][w] = dp[last][w];
            if(w - weig[i] >= 0)
                dp[curr][w-weig[i]] = max(dp[curr][w-weig[i]], dp[last][w] + prof[i]);
        }
        last = curr;
        curr = 1 - curr;
    }

    int sol = 0;
    for(auto x : dp[last])
        sol = max(sol,x);

    //sol = dp[last][G];
    fout<<sol;
    return 0;
}