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

#define oo 0x3f3f3f3f

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n, gm;;
int p[5005], gr[5005], dp[5005];

void read() {
    f>>n>>gm;
    for(int i = 1;i <= n;++i) {
        f>>gr[i]>>p[i];
    }
    f.close();
}

void solve() {
    int res = 0;
    for(int i = 1;i <= n;++i) {
        for(int j = gm;j >= 0;--j) {
            if(j + gr[i] <= gm && dp[j + gr[i]] < dp[j] + p[i]) {
                dp[j + gr[i]] = dp[j] + p[i];
                res = max(res, dp[j + gr[i]]);
            }
        }
    }
    g<<res<<'\n';
    g.close();
}

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