#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);
    }

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


    cout << dp[number - 1][W];
}

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