题目描述

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

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

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

输入格式

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

输入格式

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

样例

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

8500

数据范围

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