quarantine.cpp

#include <bits/stdc++.h>

using namespace std;
#define int long long

struct Flight
{
    int start, finish, profit;
};

bool flightComparataor(Flight s1, Flight s2)
{
    return (s1.finish < s2.finish);
}

int binarySearch(Flight flights[], int index)
{
    int lo = 0, hi = index - 1;
  
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        if (flights[mid].finish < flights[index].start)
        {
            if (flights[mid + 1].finish < flights[index].start)
                lo = mid + 1;
            else
                return mid;
        }
        else
            hi = mid - 1;
    }
  
    return -1;
}
int findMaxProfit(Flight arr[], int n)
{
    int *table = new int[n];
    table[0] = arr[0].profit;
  
    for (int i=1; i<n; i++)
    {
        int inclProf = arr[i].profit;
        int l = binarySearch(arr, i);
        if (l != -1)
            inclProf += table[l];
        table[i] = max(inclProf, table[i-1]);
    }
  
    int result = table[n-1];
    delete[] table;
  
    return result;
}

void solve(){
    int r,f,p;
    cin >> r >> f >> p;
    Flight arr[f];
    for(int i=0;i<f;i++){
        int ai,qi,pi;
        cin >> ai >> qi >> pi;
        pi = min(pi,r);
        arr[i] = {ai,ai+qi-1,pi*qi};
    }
    sort(arr, arr+f, flightComparataor);
    cout <<  findMaxProfit(arr, f)*p << "\n";
}

signed main()
{
    int t;
    cin >> t;
    while(t--)solve();
    return 0;
}