#include <bits/stdc++.h>
using namespace std;

int knapsack(int W, vector <int> &wt, vector <int> &val, int n)
{
    vector <int> dp (W + 1, 0);

    for (int i = 0; i < n; i++)
        for (int w = W; w >= wt[i]; w--)
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);


    return dp[W];
}

int main()
{
    int n, W;
    cin >> n >> W;

    vector <int> val (n);
    vector <int> wt (n);

    for (int i = 0; i < n; i++)
        cin >> wt[i] >> val[i];


    cout << knapsack(W, wt, val, n);
}