#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define MAXN 1000010
#define MAXM 2000010

ll T, n, m, ans;

struct node {
    ll num, w, h;
} a[MAXN];

bool cmp(node x, node y) {
    return x.h > y.h;
}

void solve() {
    ans = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].num >> a[i].w >> a[i].h;
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        ll h = a[i].h;
        if (a[i].num * a[i].w >= m) {
            ll k = a[i].num / (m / a[i].w);
            ans += k * h;
            a[i].num %= (m / a[i].w);
        }
    }
    ll res = m, l = 1;
    while (1) {
        if (l > n) {
            break;
        }
        if (a[l].num && res == m) {
            ans += a[l].h;
        }
        if (a[l].num == 0) {
            l++;
            continue;
        }
        if (a[l].num * a[l].w >= res) {
            if ((a[l].w == 2) && (res % 2 == 1)) {
                a[l].num -= res / 2;
                res = 1;
                for (int j = l + 1; j <= n + 1; j++) {
                    if (j == n + 1) {
                        res = m;
                        break;
                    }
                    if (a[j].w == 1 && a[j].num > 0) {
                        a[j].num--;
                        res = m;
                        break;
                    }
                }
            } else {
                a[l].num -= res / a[l].w;
                res = m;
            }
        } else {
            res -= a[l].num * a[l].w;
            a[l].num = 0;
            l++;
        }
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> T;
    while (T--)
        solve();
    return 0;
}