Stock

After years of hard work, Optiver has developed a mathematical model that predicts whether a company will be successful. This gives them a great advantage on the stock market.

In the past, Optiver made a deal with a big company that 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 its shares will become worthless.

Still, Optiver holds a large number of sell options that let them 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 the price Optiver receives per 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 calculate this.

The first line contains 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.

For each test case:

• One line with the maximum profit Optiver can achieve.