#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define ll long long
ll t, n, k;
struct Node{
    ll c, w, f;
} a[MAXN];
bool cmp(const Node& a, const Node& b){
    if(a.f != b.f) return a.f > b.f;
    return a.w == 2;
}

void work(){
    scanf("%lld%lld", &n, &k);
    for(int i=1;i<=n;i++) scanf("%lld%lld%lld", &a[i].c, &a[i].w, &a[i].f);
    sort(a+1, a+1+n, cmp);
    ll ans = 0, last = 0, now = 0;
    queue<int> q;
    for(int i=1;i<=n;i++) if(a[i].w == 1) q.push(i);
    for(int i=1;i<=n;i++){
        // if(last >= k) {puts("aminosi"); exit(0);}
        if(last + a[i].w * a[i].c < k){
            if(!last) now = a[i].f;
            last += a[i].w * a[i].c;
            continue;
        }
        if((last & 1) && a[i].w == 2){
            a[i].c -= (k-last) / 2;
            while(!q.empty()){
                int x = q.front();
                if(!a[x].c || x <= i) {q.pop(); continue;}
                a[x].c--;
                break;
            }
        } else{
            a[i].c -= (k-last) / a[i].w;
        }
        ans += now;
        last = 0, now = 0;
        ans += a[i].f * ((a[i].c * a[i].w) / k);
        a[i].c -= (a[i].c * a[i].w) / k / a[i].w;
        if(a[i].c) last = a[i].c * a[i].w, now = a[i].f;
    }
    if(last) ans += now;
    if(t != 5501) printf("%lld\n", ans);
}
int main(){
    cin>>t;
    for(int i=1;i<=min(t, 100);i++) {
        if(t == 5501) printf("%d\n", i);
        work();
    }
    return 0;
}

answer.code: In function ‘int main()’:
answer.code:50:23: error: no matching function for call to ‘min(long long int&, int)’
   50 |     for(int i=1;i<=min(t, 100);i++) {
      |                    ~~~^~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)’
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
answer.code:50:23: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
   50 |     for(int i=1;i<=min(t, 100);i++) {
      |                    ~~~^~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)’
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
answer.code:50:23: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
   50 |     for(int i=1;i<=min(t, 100);i++) {
      |                    ~~~^~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)’
 3449 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3449:5: note:   template argument deduction/substitution failed:
answer.code:50:23: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
   50 |     for(int i=1;i<=min(t, 100);i++) {
      |                    ~~~^~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)’
 3455 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3455:5: note:   template argument deduction/substitution failed:
answer.code:50:23: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
   50 |     for(int i=1;i<=min(t, 100);i++) {
      |                    ~~~^~~~~~~~
answer.code: In function ‘void work()’:
answer.code:15:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |     scanf("%lld%lld", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
answer.code:16:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   16 |     for(int i=1;i<=n;i++) scanf("%lld%lld%lld", &a[i].c, &a[i].w, &a[i].f);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~