题目描述

一家商店在 $n$ 天内销售一种商品。第 $i$ 天商店会获得 $a_i$ 件商品，商品当天即可售卖，也可储存若干天后再卖。每天商品的定价和需求量不同，第 $i$ 天商品定价为 $p_i$ ，当天最多能卖掉 $c_i$ 件。最后一天结束时，未售出商品不计入销售金额。需确定在哪些天卖出商品，可使销售总金额达到最大。

输入格式

• 第一行：一个整数 $n$ ，表示天数。
• 接下来 $n$ 行：第 $i + 1$ 行包含三个数 $a_i$、$p_i$、$c_i$ ，分别为第 $i$ 天获得的商品数量、商品定价、当天最大可售数量。

输出格式

输出一个整数，即能够获得的最大销售金额。

数据范围

• $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$ 。

样例

输入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

说明：选择囤积到最后一天再卖可获得最大销售金额。