#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

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


// int rucsac1(int n, int c, int* v, int* w, int** dp) {
//     int result;

//     //daca se afla printre solutiile salvate
//     if(dp[n][c] != 0) {
//         return dp[n][c];
//     }

//     // caz baza
//     if(n == 0 || c == 0) {
//         return 0;
//     }
    
//     if(w[n] > c) {
//         result = rucsac1(n-1, c, v, w, dp);
//         dp[n][c] = result;

//         return result;
//     }


//     result = max(rucsac1(n-1, c, v, w, dp), v[n] + rucsac1(n-1, c - w[n], v, w, dp));

//     dp[n][c] = result;

//     return result;
    
// }

int rucsac2(int n, int c, int* v, int* w, int** dp) {
 
    // cazul de bază
    for (int cap = 0; cap <= c; ++cap) {
        dp[0][cap] = 0;
    }
 
    // cazul general
    for (int i = 1; i <= n; ++i) {
        for (int cap = 0; cap <= c; ++cap) {
            // nu folosesc obiectul i => e soluția de la pasul i - 1
            dp[i][cap] = dp[i-1][cap];
 
            // folosesc obiectul i, deci trebuie să rezerv w[i] unități în rucsac
            // înseamnă ca înainte trebuie să ocup maxim cap - w[i] unități
            if (cap - w[i] >= 0) {
                int sol_aux = dp[i-1][cap - w[i]] + v[i];
 
                dp[i][cap] = max(dp[i][cap], sol_aux);
            }
        }
    }
 
    return dp[n][c];
    
}
 

int main() {
    ifstream fin;
    ofstream fout;
    ofstream dout;

    fin.open("rucsac.in");
    fout.open("rucsac.out");
    dout.open("debug.out");

    int N, C;
    fin >> N >> C;

    int* w = new int[N + 1];
    int* v = new int[N + 1];
    int**  dp = new int*[N+1];
    dp[0] = new int[C + 1];


    int v_aux, w_aux, i = 1;
    while(fin >> w_aux >> v_aux) {
        w[i] = w_aux;
        v[i] = v_aux;
        dp[i] = new int[C + 1];

        i++;
    }

    fout << rucsac2(N, C, v, w, dp);
    fin.close();
    fout.close();
    dout.close();
}