#include <bits/stdc++.h>

#define ll long long

using namespace std;

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

const int SIZE = 1005;
const int W_SIZE = 5005;

int g, w;
int cost[SIZE], profit[SIZE];
int dp[W_SIZE];

void read();
void solve();

int main()
{
    read();
    solve();
    return 0;
}

void read()
{
    fin >> g >> w;
    for(int i = 1; i <= g; ++i)
        fin >> cost[i] >> profit[i];
}

void solve()
{
    dp[0] = 0;
    int sol = 0;

    for(int i = 1; i <= g; ++i)
        for(int j = w - cost[i]; j >= 0; --j)
        {
            dp[j+cost[i]] = max( dp[j+cost[i]], dp[j] + profit[i]);
            sol = max(dp[j+cost[i]], sol);
        }

    fout << sol;
}