#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);
    dp[0] = 1;
    int maxim = dp[0];
    for (int i = 1; i <= n; i++) {
        for (int j = W - w[i]; j >= 0; j--) {
            if (dp [j] > 0) {
                dp[j + w[i]] = max(dp[j + w[i]], dp[j] + p[i]);
                if (dp[j + w[i]] > maxim) {
                    maxim = dp[j + w[i]];
                }
            }
        }
    }

    return maxim - 1;
}

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;
}