#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 5'000;
const int MAX_G = 10'000;

int dp[2][MAX_G + 1];
int w[MAX_N + 1];
int p[MAX_N + 1]; 
int n, g;
bool t;

int main() {
    fin >> n >> g;

    for (int i = 1; i <= n; i++)
        fin >> w[i] >> p[i];
    
    t = n & 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= g; j++) {
            dp[t][j] = dp[t ^ 1][j];
            if (j >= w[i] && dp[t][j] < dp[t ^ 1][j - w[i]] + p[i])
                dp[t][j] = dp[t ^ 1][j - w[i]] + p[i];
        }
        t ^= 1;
    }
    
    fout << dp[t ^ 1][g];
    
    fin.close();
    fout.close();
    return 0;
}