#include <fstream>
#include <vector>

using namespace std;

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

int main()
{
    int n, g;
    in >> n >> g;

    vector<int> w(n), p(n);

    for(int i = 0; i < n; i++)
        in >> w[i] >> p[i];

    int dp[10001] = {0};
    int profit = 0;

    for(int i = 0; i < n; i++)
        for(int j = g-w[i]; j >= 0; j--)
        {
            int disponibil = j + w[i];

            if(dp[disponibil] < dp[j] + p[i])
            {
                dp[disponibil] = dp[j] + p[i];

                if(dp[disponibil] > profit)
                    profit = dp[disponibil];
            }
        }

    out << profit;

    return 0;
}