#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; } int n, b, sup_x, sup_y, res; vector xs, ys, ps, xs_cache, ys_cache; vector > cumuls, exists; template inline T get_2dcumul(const vector >& cumuls, int y1, int x1, int y2, int 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) { int x, y, p; cin >> x >> y >> p; xs.push_back(x); ys.push_back(y); ps.push_back(p); xs_cache.push_back(x); ys_cache.push_back(y); } sort(xs_cache.begin(), xs_cache.end(), std::less()); sort(ys_cache.begin(), ys_cache.end(), std::less()); xs_cache.erase(unique(xs_cache.begin(), xs_cache.end()), xs_cache.end()); ys_cache.erase(unique(ys_cache.begin(), ys_cache.end()), ys_cache.end()); REP (i, n) { xs[i] = lower_bound(xs_cache.begin(), xs_cache.end(), xs[i]) - xs_cache.begin(); ys[i] = lower_bound(ys_cache.begin(), ys_cache.end(), ys[i]) - ys_cache.begin(); } sup_x = xs_cache.size(); sup_y = ys_cache.size(); cumuls = vector >(sup_y+1, vector(sup_x+1, 0)); exists = vector >(sup_y+1, vector(sup_x+1, 0)); REP (i, n) { int x = xs[i]; int y = ys[i]; cumuls[y+1][x+1] += ps[i]; exists[y+1][x+1] += 1; } REP (i, sup_y+1) { REP (j, sup_x) { cumuls[i][j+1] += cumuls[i][j]; exists[i][j+1] += exists[i][j]; } } REP (j, sup_x+1) { REP (i, sup_y) { cumuls[i+1][j] += cumuls[i][j]; exists[i+1][j] += exists[i][j]; } } res = 0; REP (y1, sup_y+1) { for (ll y2 = y1+1; y2 <= sup_y; y2++) { ll x1 = 0; for (ll x2 = 0; x2 <= sup_x; x2++) { while(get_2dcumul(cumuls, y1, x1, y2, x2) > b) { x1++; } res = max(res, get_2dcumul(exists, y1, x1, y2, x2)); } } } cout << res << "\n"; return 0; }