printРабочее место участника


780. Stock

Ограничения: время – 3s/6s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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.
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.

Sample Input

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

Sample Output

Source: Benelux Algorithm Programming Contest 2007