#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#define nl '\n'
#define  ull unsigned long long
using namespace std;
template<class A, class B>
A myMin(A a, B b) {
    return a < b ? a : b;
}
template<class A, class B>
A myMax(A a, B b) {
    return a > b ? a : b;
}
int V[5001][10001];
int main() {

    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    int n, g;
    vector<short> p, w;
    p.emplace_back(0);
    w.emplace_back(0);
    cin >> n >> g;
    for (int i = 1; i <= n; ++i) {
        int tw, tp;
        cin >> tw >> tp;
        p.emplace_back(tp);
        w.emplace_back(tw);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= g; ++j) {
            V[i][j] = V[i-1][j];
            if (w[i] <= j) {
                V[i][j] = myMax(V[i-1][j-w[i]] + p[i],V[i][j]);
            }
        }
    }
    cout << V[n][g];
    return 0;
}