Integers Shop solution codeforces
The integers shop sellssegments. The -th of them contains all integers from to and costs coins.
Tomorrow Vasya will go to this shop and will buy some segments there. He will get all integers that appear in at least one of bought segments. The total cost of the purchase is the sum of costs of all segments in it.
After shopping, Vasya will get some more integers as a gift. He will get integeras a gift if and only if all of the following conditions are satisfied: Integers Shop solution codeforces
- Vasya hasn’t bought .
- Vasya has bought integer that is less than .
- Vasya has bought integer that is greater than .
Vasya can get integeras a gift only once so he won’t have the same integers after receiving a gift.
For example, if Vasya buys segmentfor coins and segment for coins, he spends coins and receives integers from these segments. He also gets integers and as a gift.
Due to the technical issues only the firstsegments (that is, segments ) will be available tomorrow in the shop.
Vasya wants to get (to buy or to get as a gift) as many integers as possible. If he can do this in differents ways, he selects the cheapest of them.
For eachfrom to , find how many coins will Vasya spend if only the first segments will be available.
The first line contains a single integer( ) — the number of test cases.
The first line of each test case contains the single integer( ) — the number of segments in the shop.
Each of nextlines contains three integers , , ( ) — the ends of the -th segments and its cost.
It is guaranteed that the total sum ofover all test cases doesn’t exceed .
For each test case outputintegers: the -th ( ) of them should be the number of coins Vasia will spend in the shop if only the first segments will be available.
3 2 2 4 20 7 8 22 2 5 11 42 5 11 42 6 1 4 4 5 8 9 7 8 7 2 10 252 1 11 271 1 10 1
20 42 42 42 4 13 11 256 271 271
In the first test case ifthen Vasya can buy only the segment for coins and get integers.
The way to getintegers for coins in case is described in the statement.
In the second test case note, that there can be the same segments in the shop.