Story of Seasons

#include   <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>


using namespace std;
// using namespace __gnu_pbds;


#define  endl            '\n'
#define  pb              push_back
#define  rep(i,a,n)      for(ll i =a;i<n;i++)
#define  min3(a,b,c)     min(a,min(b,c))
#define  min4(a,b,c,d)   min(a,min(b,min(c,d)))
#define  max3(a,b,c)     max(a,max(b,c))
#define  max4(a,b,c,d)   max(a,max(b,max(c,d)))
#define  mod             1000000007
#define  fastio()        ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define  ss              second
#define  ff              first
#define  gcd             __gcd
#define  all(x)          x.begin(),x.end()
#define  wttt            while(t--)
#define  printall(v)     for(auto value:v) cout<<value<<" ";cout<<endl;
#define  mp              make_pair
#define  PI              3.141592653589793238462643383279502884197
#define  ub              upper_bound
#define  lb              lower_bound
#define  read(v,n)       rep(i,0,n)cin>>v[i];
#define  count_set_bits  __builtin_popcountll



#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
#else
#define debug(x);
#endif


typedef long long int ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef pair<ll,ll>pll;
typedef map<ll,ll> mll;
typedef vector<vector<ll>> vvll;
typedef vector<pair<ll,ll>> vpll;
typedef vector<ld> vld;
typedef vector<char> vch;
typedef vector<vector<char>> vvch;
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > pbds;

ld eps = 1e-9;

/*
For using ordered_set :

1. *s.find_by_order(k) --> Returns the element present at index k.

2.  s.order_of_key(k) -->  Returns the number of elements smaller than k.
*/





void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(ld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
// void _print(pbds v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T> void _print(set <T, greater<T>> v);
template <class T, class V> void _print(map <T, V> v);
template <class T, class V> void _print(multimap <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T> void _print(multiset <T, greater<T>> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T, greater<T>> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T, greater<T>> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}


















void solve()

{
    ll d, n, x;
    cin>>d>>n>>x;
    map<ll, vpll> m;
    rep(i,0,n)
    {
        ll q,l,v;cin>>q>>l>>v;
        ll day = d - l;
        if(day < 1)
        {
            continue;
        }
        m[day].pb({v, q});
    }

    vll days = {0};
    for(auto val:m)
    {
        days.pb(val.ff);
    }
    debug(days);
    reverse(all(days));
    ll tot = 0, ans = 0;
    multiset<pll, greater<pll>> s;
    rep(i,0,days.size() - 1)
    {
        ll curr = days[i], next = days[i+1];
        tot = tot + (curr - next)*x;
        for(pll val:m[curr])
        {
            s.insert(val);
        }
        debug(s);
        while(s.size() > 0 && tot > 0)
        {
            pll it = (*s.begin());
            s.erase(s.begin());
            if(tot >= it.ss)
            {
                tot -= it.ss;
                ans += (it.ss * it.ff);
            }
            else
            {
                ans += (it.ff * tot);
                it.ss -= tot;
                s.insert(it);
                tot = 0;
            }
        }
    }

    cout<<ans<<endl;

}










int main()
{
      #ifndef ONLINE_JUDGE
      freopen("Error.txt", "w", stderr);
      #endif

      fastio();

      ll t=1;
      //pre();

      cin>>t;



      for(ll ttt = 1;ttt<=t;ttt++)
      {


           cout<<"Case #"<<ttt<<": ";


        solve();


      }



      return 0;
}