#pragma GCC optimize "O2"
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <queue>
// for iota, accumulate, partial_sum
// #include <numeric>
// #include <iomanip>
// #include <fstream>
// #include <deque>
// #include <cmath>
// #include <unordered_map>
// #include <utility>
// #include <unordered_set>
// #include <ctime>
// #include <stack>
// #include <bitset>
// #include <random>
// #include <cstring>
// #include <cassert>
// #include <complex>
using namespace std;
typedef unsigned long long int lu;
typedef long long int ll;
typedef long double ld;
#define v vector<ll>
#define vu vector<lu>
#define vvu vector<vector<lu>>
#define vld vector<ld>
#define vs vector<string>
#define pll pair<ll, ll>
#define vpll vector<pair<ll, ll>>
#define puu pair<lu, lu>
#define vpuu vector<pair<lu, lu>>
const lu MOD = 1000000007;
const ld PI = 2 * acos(0.0);
#define round(x, y) ((x + y - 1) / y)
#define ce(x, y) ((x + y - 1) / y)
#define amax(x, y) \
    if (y > x)     \
        x = y;
#define amin(x, y) \
    if (y < x)     \
        x = y;
#define lcm(x, y) ((x) * (y) / __gcd(x, y))
#define sq(x) ((x) * (x))
#define cb(x) ((x) * (x) * (x))

#define all(x) x.begin(), x.end()

v ga(ll n)
{
    v a;
    for (ll i = 0; i < n; i++)
    {
        ll p;
        // scanf("%lld", &p);
        cin >> p;
        a.push_back(p);
    }
    return move(a);
}

vu gau(lu n)
{
    vu a;
    for (lu i = 0; i < n; i++)
    {
        lu p;
        // scanf("%lu", &p);
        cin >> p;
        a.push_back(p);
    }
    return move(a);
}
vs gas(lu n)
{
    vs a;
    for (lu i = 0; i < n; i++)
    {
        string p;
        // scanf("%lu", &p);
        cin >> p;
        a.push_back(p);
    }
    return move(a);
}

template <typename T, typename A>
void pa(vector<T, A> const &a)
{
    for (T p : a)
    {
        // printf("%lu ", a[i]);
        cout << p << " ";
    }
    cout << "\n";
}

void yes()
{
    cout << "YES\n";
}

void no()
{
    cout << "NO\n";
}

void yesno(int f)
{
    if (f)
        yes();
    else
        no();
}

void solve()
{
    lu n, w;
    cin >> n >> w;
    vpuu data;
    for (lu i = 0; i < n; i++)
    {
        lu a, b;
        cin >> a >> b;
        data.push_back(make_pair(a, b));
    }
    data.insert(data.begin(), make_pair(0, 0));

    vvu knapsack(n + 1, vu(w + 1, 0));
    // knapsack(n,w)=maximum value you can get with first n elements
    // whose weight no exceeds w

    // build bottom up
    // 0 elements, 1 element, 2 elements, etc.

    lu m = 0;

    for (lu count = 0; count <= n; count++)
    {
        for (lu weight = 0; weight <= w; weight++)
        {
            // nowhere to get any value
            if (count == 0 || weight == 0)
            {
                knapsack[count][weight] = 0;
            }
            else if (weight >= data[count].first)
            {
                // either include the current element or don't include it. take max of both ways
                knapsack[count][weight] = max(knapsack[count - 1][weight], knapsack[count - 1][weight - data[count].first] + data[count].second);
                amax(m, knapsack[count][weight]);
            }
            else
            {
                knapsack[count][weight] = knapsack[count - 1][weight];
            }
        }
    }

    for (vu row : knapsack)
    {
        // pa(row);
    }

    cout << m;
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
    return 0;
}

Measured memory_bytes: 80256