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

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

int n, gmax, g[5005], p[5005];
int dp[2][10005]; // doar linia 0 si linia 1
int main() {
    // cout << sizeof(dp) / 1024.0 << "kb";
    fin >> n >> gmax;
    for (int i = 1; i <= n; i ++) {
        fin >> g[i] >> p[i];
    }
    int cr = 1; // indicele liniei curente
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= gmax; j ++) {
            if (j-g[i] >= 0)
                dp[cr][j] = max(dp[1 - cr][j], dp[1 - cr][j-g[i]]+p[i]);
            else
                dp[cr][j] = dp[1 - cr][j];
        }
        cr = 1 - cr; // din 1 devine 0 si din 0 devine 1
    }
    fout << dp[1 - cr][gmax];
    return 0;
}