#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm> // Pentru funcția max()

using namespace std;

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

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

    // Citim greutatile si profiturile pentru cele 'n' obiecte
    vector<int> W(n); // Weight (greutatea)
    vector<int> P(n); // Profitul (valoarea)
    
    for(int i = 0; i < n; i++) {
        fin >> W[i] >> P[i];
    }

    // dp[j] = profitul maxim pe care il putem obtine avand greutatea maxima j
    // Il initializam cu 0, de dimensiune G + 1
    vector<int> dp(G + 1, 0);

    // AICI URMEAZĂ LOGICA DE PROGRAMARE DINAMICĂ
    // ...
    // ...
    for(int i = 0; i < n; i++) {
        // Parcurgem greutățile INVERS, de la capacitatea maximă până la greutatea obiectului curent
        for(int j = G; j >= W[i]; j--) {
            // Recurența:
            // dp[j] rămâne cum era (nu luăm obiectul) 
            // SAU
            // devine (profitul obiectului curent) + (profitul maxim pentru restul de greutate: j - W[i])
            dp[j] = max(dp[j], dp[j - W[i]] + P[i]);
        }
    }


    // La final, raspunsul va fi in dp[G]
    fout << dp[G] << "\n";

    return 0;
}