#include<iostream>
#include<vector>
#include<fstream>

using namespace std;

int main() {
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");

    int N, G, i, j;
    in >> N >> G;

    //dp[i][j] = profitul maxim care se poate obtine pentru un rucsac
    //cu i obiecte si greutate j
    vector<vector<int>> dp(N + 1, vector<int> (G + 1, 0));

    vector<int> w(N + 1);
    vector<int> p(N + 1);

    for (i = 1; i <= N; i++)
        in >> w[i] >> p[i];

    for (j = 0; j <= G; j++)
        dp[0][j] = 0; //nu am obiecte, nu pot obtine niciun profit 
    
    for (i = 1; i <= N; i++)
        for (j = 0; j <= G; j++)
            if (j - w[i] >= 0)
                dp[i][j] = max (dp[i - 1][j], dp[i - 1][j - w[i]] + p[i]);
            else
                dp[i][j] = dp[i - 1][j];

    out << dp[N][G];
}