#include <bits/stdc++.h>

using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int n, gm, w[5005], p[5005], d[10005];
int main()
{
    in >> n >> gm;
    for (int i = 1; i <= n; i++) {
        in >> w[i] >> p[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = gm; j >= 0; j--) {
            if (j - w[i] >= 0) {
                d[j] = max(d[j], d[j - w[i]] + p[i]);
                ans = max(ans, d[j]);
            }
        }

    out << ans << '\n';
    return 0;
}