#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 2x(W+1)
    vector< vector<int> > dp(2);
    for (int i = 0; i <= 1; ++i) {
        dp[i].resize(W + 1);
    }

    // cazul de baza
    for (int cap = 0; cap <= W; ++cap) {
        dp[0][cap] = 0;
    }

    int line = 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[1 - line][cap] = dp[line][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 = dp[line][cap - w[i]] + p[i];
                
                dp[1 - line][cap] = max(dp[1 - line][cap], sol_aux);
            }
        }

        line = 1 - line;
    }

    return dp[line][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;
}