Maximizing Payment from Non-overlapping Contracts

Emily is a contractor who has been offered several contracts. Each contract is characterized by a start time \(s_i\), an end time \(e_i\), and a payment \(p_i\). However, she cannot work on overlapping contracts. Two contracts are non-overlapping if the end time of one is strictly less than the start time of another.

Your task is to help Emily determine the maximum total payment she can earn by selecting an optimal subset of non-overlapping contracts. This problem can be efficiently solved using a dynamic programming approach combined with binary search with a time complexity of \(O(N \log N)\), where \(N\) is the number of contracts in a test case.

Input and Output Format

The input starts with an integer \(T\) denoting the number of test cases. Each test case begins with an integer \(N\) representing the number of contracts, followed by \(N\) lines each containing three integers \(s\), \(e\) and \(p\) indicating the start time, end time, and payment for a contract.

For each test case, print a single integer which is the maximum total payment obtainable by selecting non-overlapping contracts.

inputFormat

The first line contains an integer (T) denoting the number of test cases. For each test case, the first line contains an integer (N) - the number of contracts. The next (N) lines each contain three space-separated integers (s), (e), and (p), representing the start time, end time, and payment of a contract respectively.

outputFormat

For each test case, output one line containing a single integer: the maximum total payment that can be achieved by selecting non-overlapping contracts.## sample

2
3
1 3 50
2 5 20
4 6 10
2
1 2 10
2 3 20

60
20