## Дата и время

04/06/2023 13:07:38

## Авторизация

 Имя: Пароль:
Зарегистрироваться
Восстановить пароль

# Тренировка 3

## J. Stock

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

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\ ≤\ 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.
Output
For each testcase:
One line with the maximum profit Optiver can achieve.

Sample Input

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


Sample Output

76

Source: Benelux Algorithm Programming Contest 2007