#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

int rucsac(int n, int W, vector<int> &w, vector<int> &p) {
    // dp este o matrice de dimensiune (n + 1)x(W+1)
    // pentru ca folosim dp[0][*] pentru multimea vida
    //                   dp[*][0] pentru situatia in care ghiozdanul are capacitate 0
    vector<int> dp(W + 1), aux(W + 1);

    //cazul de baza
    dp[0] = 0;
    aux[0] = 0;

    // cazul general
    for (int i = 1; i <= n; ++i) {
        for (int cap = 0; cap <= W; ++cap) {
            // nu folosesc obiectu i => e solutia de la pasul i - 1
            dp[cap] = aux[cap];

            // folosesc obiectul i, deci trebuie sa rezerv w[i] unitati in rucsac
            // inseamna ca inainte trebuie sa ocup maxim cap - w[i] unitati
            if (cap - w[i] >= 0) {
                int sol_aux = aux[cap - w[i]] + p[i];

                dp[cap] = max(dp[cap], sol_aux);
            }
        }

        dp.swap(aux);
    }

    return aux[W];
}

int main() {
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    int n, W;
    vector<int> p, w;

    // citeste datele
    cin >> n >> W;
    p.resize(n + 1); // redimensioneaza v sa aiba n elememnte
    w.resize(n + 1); // redimensioneaza v sa aiba n elememnte

    for (int i = 1; i <= n; ++i)
    {
        cin >> w[i] >> p[i];
    }

    // afiseaza solutia
    cout << rucsac(n, W, w, p) << "\n";

    return 0;
}