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

using namespace std;

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


int rucsac(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 = rucsac(n-1, c, v, w, dp);
        dp[n][c] = result;

        return result;
    }


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

    dp[n][c] = result;

    return result;
    
}
 

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 << rucsac(N, C, v, w, dp);
    fin.close();
    fout.close();
    dout.close();
}