销售商品

题目描述

有一家商店正在销售一种商品。在 $n$ 天时间里，每天都会得到不同数量的商品，其中在第 $i$ 天，会得到 $a_i$ 件商品，商品在获得的当天就可以卖出，也可以屯若干天再卖。

商品每天的定价和需求量是不同的，在第 $i$ 天，商品市场定价为 $p_i$，在这一天，最多可以卖掉 $c_i$ 件。最后一天结束后，没有卖出的商品不算入销售金额。

请问，应该在哪些天卖出商品，才能使得销售总金额达到最大。

输入格式

第一行：单个整数 $n$。

接下来有 $n$ 行：第 $i+1$ 行第 $i$ 天的数据：$a_i$, $p_i$ 和 $c_i$。

输出格式

单个整数：表示能够获得的最大销售金额。

样例输入 #1

4
10 100 10
10 300 15
10 500 5
10 1000 1

样例输出 #1

8500

样例输入 #2

3
1 10 100
1 100 100
1 1000 100

样例输出 #2

3000

样例说明 #2

囤积到最后一天再卖。

数据范围

• $0\le a_i\le 10^6$；
• $1\le p_i\le 10^6$；
• $0\le c_i\le 10^6$；
• 对于 30% 的数据，$n\le 100$；
• 对于 60% 的数据，$n\le 10000$；
• 对于 100% 的数据，$1\le n\le 100000$。

测试点分布