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

using namespace std;

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

const int MAX_N = 5001;
const int MAX_G = 10001;

int wt[MAX_N], val[MAX_N];
int obiecte, greutate;

// Corectat: Dimensiunea vectorului este MAX_G + 1
int dp[MAX_G + 1]; 

int maxim(int a, int b) {
    return (a > b ? a : b);
}

void citire() {
    in >> obiecte >> greutate;
    int a, b;
    // Citim de la 1
    for (int i = 1; i <= obiecte; i++) {
        in >> a >> b;
        wt[i] = a;
        val[i] = b;
    }
}

void solve_dp() {
    // Iterăm prin obiecte de la 1 la N
    for (int i = 1; i <= obiecte; i++) {
        // Iterăm descrescător prin greutăți
        // Folosim wt[i] și val[i]
        for (int j = greutate; j >= wt[i]; j--) {
            dp[j] = maxim(dp[j], val[i] + dp[j - wt[i]]);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    in.tie(NULL);
    out.tie(NULL);
    
    citire();
    solve_dp();
    
    // Corectat: Afișăm dp[greutate]
    out << dp[greutate];

    in.close();
    out.close();
    return 0;
}