#include <fstream>
#include <iostream>
#include <queue>
#include <bitset>
#include <stack>
#include <unordered_map>
#include <vector>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n, G, w[5001], val[5001];
int dp[2][10001]; ///dp[i][j] = suma profiturilor maxima din primele i obiecte avand greutate totala j

int main() {
    int s = 0;
    fin >> n >> G;
    for (int i = 1; i <= n; i++)
        fin >> w[i] >> val[i];
    int lin = 1;

    dp[0][w[1]] = val[1];
    s = w[1];
    for (int i = 2; i <= n; i++) {
        s += w[i];
        for (int j = 0; j <= min(s,G); j++) {
            dp[lin][j] = dp[1 - lin][j];
            if (j >= w[i])
                dp[lin][j] = max(dp[lin][j], dp[1 - lin][j - w[i]] + val[i]);
        }
        lin = 1 - lin;
    }
    int maxs = 0;
    for (int i = 0; i <= min(G, s); i++)
        maxs = max(maxs, dp[1 - lin][i]);
    fout << maxs;
    return 0;
}