Optiver sponsored problem.
After years of hard work Optiver has developed a mathematical model that allows them
to predict wether or not a company will be succesful. This obviously gives them a great
advantage on the stock market.
In the past, Optiver made a deal with a big company, which forces them to buy shares of
the company according to a fixed schedule. Unfortunately, Optiver’s model has determined
that the company will go bankrupt after exactly n days, after which their shares will become
worthless.
Still, Optiver holds a large number of sell options that allows them to sell some of the
shares before the company goes bankrupt. However, there is a limit on the number of
shares Optiver can sell every day, and price Optiver receives for a share may vary from
day to day. Therefore, it is not immediately clear when Optiver should sell their shares to
maximize their profit, so they asked you to write a program to calculcate this.
Input
On the first line an integer t (1 ≤ t ≤ 100): the number of test cases. Then for each test
case:
• One line with an integer n (1 ≤ n ≤ 100 000): the number of days before the company
goes bankrupt.
• n lines with three integers xi (0 ≤ xi ≤ 100), pi (0 ≤ pi ≤ 100) and mi (0 ≤
mi ≤ 10 000 000): the number of shares Optiver receives on day i, the (selling) price
per share on day i, and the maximum number of shares Optiver can sell on day i,
respectively.
Output
For each test case:
• One line with the maximum profit Optiver can achieve.

Sample in- and output
Input
1
6
4 4 2
2 9 3
2 6 3
2 5 9
2 2 2
2 3 3

Output

76

数据范围大的可怕

100组数据，每组100000天，给出每天获得股票数量，股票价格，当天可卖出的股票数量

然后求最大获利。。。

倒序。。。然后由于股票价格<=100。。。可以用set在几乎常数时间内得到这天之后的可卖的最高价格，然后和当前价格一起选高的卖，如果当天卖出股票数量有剩余的加入set

复杂度100*100000*log(100)