#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int knapsack(int N, int G, vector<int> &weights, vector<int> &values)
{
    vector<int> dp(G + 1, 0);

    for (int i = 0; i < N; i++)
    {
        for (int w = G; w >= weights[i]; w--)
        {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }

    return dp[G];
}

int main()
{
    ifstream inFile("rucsac.in");
    ofstream outFile("rucsac.out");

    if (!inFile || !outFile)
    {
        cerr << "Eroare la deschiderea fisierelor!" << endl;
        return 1;
    }

    int N, G;
    inFile >> N >> G;

    vector<int> weights(N), values(N);
    for (int i = 0; i < N; i++)
    {
        inFile >> weights[i] >> values[i];
    }

    int result = knapsack(N, G, weights, values);
    outFile << result << endl;

    inFile.close();
    outFile.close();

    return 0;
}