Тренировка 3

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.

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\ ≤\ 100000)`: the number of days before the company goes bankrupt.

n lines with three integers `x_i` `(0\ ≤\ x_i\ ≤\ 100)`, `p_i` `(0\ ≤\ p_i\ ≤\ 100)` and `m_i` `(0\ ≤\ m_i\ ≤\ 10000000)`: 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.

For each testcase:

One line with the maximum profit Optiver can achieve.

1
6
4 4 2
2 9 3
2 6 3
2 5 9
2 2 2
2 3 3

76