[CQOI2012]模拟工厂

内存限制：256 MB 时间限制：1000 ms

有一个称为“模拟工厂”的游戏是这样的：在时刻 $0$，工厂的生产力等于 $1$。在每个时刻，你可以提高生产力或者生产商品。如果选择提高生产力，在下一个时刻时工厂的生产力加 $1$；如果选择生产商品，则下一个时刻你所拥有的商品数量增加 $p$，其中 $p$ 是本时刻工厂的生产力。

有 $n$ 个订单，可以选择接受或者不接受。第 $i$ 个订单 $(t_i,g_i,m_i)$ 要求在时刻 $t_i$ 给买家提供 $g_i$ 个商品，事成之后商品数量减少 $g_i$，而收入增加 $m_i$ 元。如果接受订单 $i$，则必须恰好在时刻 $t_i$ 交易，不能早也不能晚。同一时刻可以接受多个订单，但每个订单只能被接受一次。要求最后的总收入最大。

例如，如果一共有两个订单 $(5,1,8)$ 和 $(7,15,3)$，用如下策略是最优的：时刻 $0, 1, 2$ 提高生产力（时刻 $3$ 的生产力为 $4$），然后在时刻 $3$，$4$ 生产商品，则在时刻 $5$ 时将拥有 $8$ 个商品。此时接受第 $1$ 个订单（还会剩下 $7$ 个商品），并且在时刻 $5$，$6$ 继续生产商品，则在时刻 $7$ 时拥有 $7+4+4=15$ 个商品，正好满足订单 $2$。

输入第一行包含一个整数 $n$，即订单数目。以下 $n$ 行每行三个整数 $t_i,g_i,m_i$。

输出仅一行，为最大总收入。输出保证在 $32$ 位带符号整数范围内。

样例输入 1

2
5 1 8
7 15 3

样例输出 1

$\begin{array}{|c|c|c|c|}\hline 编号 & 1-3 & 4-6 & 7-10 \\ \hline n & \le 5 & \le 10 & \le 15 \\ \hline t_i & 100 & 100 & \le 100000 \\ \hline g_i & 10000 & 10000 & \le 10^9 \\ \hline m_i & 10000 & 10000 & \le 10^9 \\ \hline \end{array}$

C1435 [CQOI2012]模拟工厂

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

提示