#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define oo 0x3f3f3f3f

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n, m;;
int dp[5005];
vector<pair<int, int>> gv;

void read() {
    int x, y;
    f>>n>>m;
    for(int i = 1;i <= n;++i) {
        f>>x>>y;
        gv.push_back(make_pair(x, y));
    }
    f.close();
}

void solve() {
    int res = 0;
    for(const auto& pr : gv) {
        for(int i = m - pr.first;i >= 0;--i) {
            dp[i + pr.first] = max(dp[i + pr.first], dp[i] + pr.second);
            res = max(res, dp[i + pr.first]);
        }
    }
    g<<res<<'\n';
    g.close();
}

int main() {
    read();
    solve();
    return 0;
}