/* n <= 1e3 t <= 1e6 y <= 2e3 x <= 1e6 */ // In the name of God. // Ya Ali! #include //#define int long long using namespace std; const int maxn = 1e3 + 17, inf = 1e6 + 1; int n, t, dp[maxn], sx[maxn], ex[maxn], y[maxn], h[maxn], cost[maxn], per[maxn]; void fix(int &x){ if(x > inf) x = inf; } void solve() { memset(dp, 63, sizeof dp); dp[0] = 0; memset(h, 63, sizeof dp); h[0] = 0; assert(cin >> n >> t); for(int i = 0; i < n; i++) cin >> y[i] >> sx[i] >> ex[i]; iota(per, per + n, 0); sort(per, per + n, [](int i, int j){ if(y[i] != y[j]) return y[i] < y[j]; return sx[i] < sx[j]; }); int ly = 0; for(int i = 0, j = 0; i < n; i = j){ int lx = 0; while(j < n && y[ per[j] ] == y[ per[i] ]){ fix(cost[j - i + 1] = sx[ per[j] ] - lx + (ex[ per[j] ] - sx[ per[j] ]) + cost[j - i]); lx = ex[ per[j] ]; j++; } int cy = y[ per[i] ]; for(int i = 0; i <= n; i++) fix(h[i] += cy - ly); for(int t = n; t >= 0; t--) for(int k = 0; k <= t && k <= j - i; k++){ int my = cost[k] + h[t - k]; dp[t] = min(dp[t], my); h[t] = min(h[t], my + (k ? ex[per[ i + k - 1] ] : 0)); } ly = cy; } cout << upper_bound(dp, dp + n + 1, t) - dp - 1 << '\n'; } int main() { ios::sync_with_stdio(0), cin.tie(0); int t; cin >> t; while(t--) solve(); }