#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[N + 1], v [C + 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();
}