#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
using namespace std;

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

// const int n = 3, g = 6;
// int w[] = {0, 1, 2, 3}, p[] = {0, 10, 15, 40}; // greutate / profit
// int dp[n + 1][g + 1];                          // dp[i][j] = profitul maxim obtinut cu primele i obiecte si greutatea j

// void printMat()
// {
//     for (int i = 0; i <= n; i++, cout << endl)
//         for (int j = 0; j <= g; j++)
//             cout << setw(3) << dp[i][j] << " ";
// }

int main()
{
    int n, w;
    fin >> n >> w;

    vector<vector<long long>> dp(2, vector<long long>(w + 1, 0));

    bool x = 1;
    for (int i = 1; i <= n; i++)
    {
        int wi, vi;
        fin >> wi >> vi;
        for (int j = 0; j <= w; j++)
        {
            dp[x][j] = dp[x ^ 1][j];
            if (wi <= j && dp[x ^ 1][j - wi] + vi > dp[x][j])
                dp[x][j] = dp[x ^ 1][j - wi] + vi;
        }
        x ^= 1;
    }

    long long ans = 0;
    for (int i = 0; i <= 1; i++)
        for (int j = 0; j <= w; j++)
            ans = max(ans, dp[i][j]);

    fout << ans << '\n';
    return 0;
}