#include <iostream>
#include <fstream>
using namespace std;

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

const int maxn = 5005;
const int maxg = 10005;
int W[maxn], P[maxn], Dp[maxg];

int main() {
    ios_base :: sync_with_stdio (false);
    int n, g, i, j, ans = 0;
    fin >> n >> g;
    for (i = 1; i <= n; i++) {
        fin >> W[i] >> P[i];
    }
    Dp[0] = 0;
    for (i = 1; i <= n; i++) {
        for (j = g - W[i]; j >= 0; j--) {
            if (Dp[j + W[i]] < Dp[j] + P[i]) {
                Dp[j + W[i]] = Dp[j] + P[i];
                if (Dp[j + W[i]] > ans) {
                    ans = Dp[j + W[i]];
                }
            }
        }
    }
    fout << ans << "\n";
    fin.close();
    fout.close();
    return 0;
}