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

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

const int maxn = 5e3 + 5;
const int maxg = 1e4 + 5;
int P[maxn], W[maxn], Dp[maxg];

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