#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int maximum(int a, int b)
{
    if (a > b)
        return a;
    return b;
}

void knapsack()
{
    int number, W;
    cin >> number >> W;
    vector<int> w, v;
    for(int i = 0; i < number; ++i)
    {
        int a, b;
        cin >> a >> b;
        w.push_back(a);
        v.push_back(b);
    }

    vector<int> dp1(W + 1, 0), dp2(W + 1, 0);
    for(int j = 0; j < w[0]; ++j)
        dp1[j] = 0;
    for(int j = w[0]; j <= W; ++j)
        dp1[j] = v[0];
    for(int i = 1; i < number; ++i)
    {
        for(int j = 0; j <= W; ++j)
            if(w[i] > j)
            {
                    dp2[j] = dp1[j];
            }
            else
                dp2[j] = maximum(dp1[j], dp1[j - w[i]] + v[i]);
        dp1 = dp2;
    }

    cout << dp2[W];
}

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    knapsack();
    return 0;
}