#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <string>
#include <unordered_set>
#include <cmath>
#include <functional>
#include <stack>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

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

    int n, g;
    cin >> n >> g;
    vector<int> dp1(g + 1), dp2(g + 1);
    vector<pair<int, int>> v(n);

    for (int i = 0; i < n; i++)
        cin >> v[i].first >> v[i].second;
    for (int i = 0; i < n; i++)
    {
        dp1 = dp2;
        for (int w=0;w<=g;w++)
            if (w == 0 || dp1[w] != 0)
            {
                int w2 = w + v[i].first;
                if (w2 <= g)
                    dp2[w2] = max(dp2[w2], dp1[w] + v[i].second);
            }
    }
    int maxim = 0;
    for (int i : dp2)
        maxim = max(i, maxim);
    cout << maxim << '\n';
    return 0;
}