/*
ID: rchalam1
LANG: C++14
TASK:
*/
// For train.usaco.org, fill the template above.

// Competitive Coding Template

// GCC OPTIMIAZTION FLAGS
#ifdef ONLINE_JUDGE
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

/*
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
*/
// All Includes for Competitive Coding Template

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

using vi = std::vector<int>;
using vll = std::vector<long long>;
using vull = std::vector<unsigned long long>;

#define FOR(i, a, b) for (auto i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (auto i = (a); i >= (b); --i)
#define R0F(i, a) ROF(i, a, 0)
#define ITR(a, x) for (auto& a: x)

#define FSRT(set) sort((set).begin(),(set).end())
#define RSRT(set) sort((set).rbegin(),(set).rend())
#define CSRT(set, function) sort((set).begin(),(set).end(), (function))
#define TRS(set) sort((set).begin(),(set).end(), greater<>())
#define REV(set) reverse((set).begin(),(set).end());

#define ALL(set) (set).begin(), (set).end()

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound

// For stdio, call setIO() or setIO("").
void setIO(std::ifstream &readFile, std::ofstream &writeFile, const std::string &name = "", bool stdIO = false)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	if(!name.empty() && !stdIO)
	{
		readFile.open(name + ".in");
		if(readFile.fail()) return;
		writeFile.open(name + ".out");
		std::cin.rdbuf(readFile.rdbuf());
		std::cout.rdbuf(writeFile.rdbuf());
	}
}

// To time program, create object Timer  to start timing, and call Timer.elapsed().
#include <chrono>

class Timer
{
	std::chrono::time_point<std::chrono::high_resolution_clock> m_beg;
public:
	Timer() : m_beg(std::chrono::high_resolution_clock::now())
	{}

	void reset()
	{ m_beg = std::chrono::high_resolution_clock::now(); }

	[[nodiscard]] long double elapsed() const
	{
		return std::chrono::duration_cast<std::chrono::duration<long double, std::ratio<1> >>(
				std::chrono::high_resolution_clock::now() - m_beg).count();
	}
};

struct customHash
{
	static uint64_t splitmix64(uint64_t x)
	{
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const
	{
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}

	size_t operator()(pair<uint64_t, uint64_t> x) const
	{
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x.first + FIXED_RANDOM) ^ (splitmix64(x.second + FIXED_RANDOM) >> 1);
	}
};

// Defines datatype
using dt = ll;
// Defines MAXN value
constexpr dt MAXN = 1e5 + 1;
// Defines INFINITE Value
constexpr dt INF = 1e9 + 1;
// Defines Modulus
constexpr dt MOD = 1e9 + 7;
// Defines Floating Point Correction
constexpr long double EPS = 1e-9;

//*****
//START CODE BELOW
//*****

void solve()
{
	ll n, w;
	cin >> n >> w;
	vector<ll> weights(n), values(n);
	for(ll i = 0; i < n; ++i) cin >> weights[i] >> values[i];
	vector<vector<ll>> dp(n + 1, vector<ll>(w + 1, 0));
	for(ll i = 1; i <= n; ++i)
		for(ll j = 0; j <= w; ++j)
			dp[i][j] = max(dp[i - 1][j], j >= weights[i - 1] ? dp[i - 1][j - weights[i - 1]] + values[i - 1] : 0);
	cout << dp[n][w] << '\n';
}

int main(int argc, char *argv[])
{
	static std::ifstream readFile;
	static std::ofstream writeFile;
	setIO(readFile, writeFile);
	ll t = 1;
	//cin >> t;
	while(t--) solve();
}

Measured memory_bytes: 83116