#include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long int; #define REP(i, n) for(int i = 0; i < (int)(n); i++) #define YES(n) std::cout << ((n) ? "YES" : "NO" ) << "\n"; #define Yes(n) std::cout << ((n) ? "Yes" : "No" ) << "\n"; #define ALL_INCLUDED_ENVIRONMENT template class C> std::ostream& operator<<(std::ostream& o, const C& v) { o << "{"; bool init = 1; for (auto e : v) { if (init) { init = 0; } else { o << ", "; } o << e; } o << "}"; return o; } ll n, b, sup, res; vector xs, ys, ps, cache; vector > cumuls, exists; template T get_2dcumul(const vector >& cumuls, long long y1, long long x1, long long y2, long long x2) { return cumuls[y2][x2] - cumuls[y2][x1] - cumuls[y1][x2] + cumuls[y1][x1]; } int main() { // cin.tie(0); // ios::sync_with_stdio(false); cin >> n >> b; REP (i, n) { ll x, y, p; cin >> x >> y >> p; xs.push_back(x); ys.push_back(y); ps.push_back(p); cache.push_back(x); cache.push_back(y); } sort(cache.begin(), cache.end(), std::less()); cache.erase(unique(cache.begin(), cache.end()), cache.end()); REP (i, n) { xs[i] = lower_bound(cache.begin(), cache.end(), xs[i]) - cache.begin(); ys[i] = lower_bound(cache.begin(), cache.end(), ys[i]) - cache.begin(); } sup = cache.size(); cumuls = vector >(sup+1, vector(sup+1, 0)); exists = vector >(sup+1, vector(sup+1, 0)); REP (i, n) { ll x = xs[i]; ll y = ys[i]; cumuls[y+1][x+1] += ps[i]; exists[y+1][x+1] += 1; } REP (i, sup+1) { REP (j, sup) { cumuls[i][j+1] += cumuls[i][j]; exists[i][j+1] += exists[i][j]; } } REP (j, sup+1) { REP (i, sup) { cumuls[i+1][j] += cumuls[i][j]; exists[i+1][j] += exists[i][j]; } } res = 0; REP (y1, sup+1) { REP (x1, sup+1) { for (ll y2 = y1 + 1; y2 <= sup; y2++) { for (ll x2 = x1 + 1; x2 <= sup; x2++) { if (get_2dcumul(cumuls, y1, x1, y2, x2) <= b) res = max(res, get_2dcumul(exists, y1, x1, y2, x2)); } } } } cout << res << "\n"; return 0; }