[CQOI2012] 模拟工厂
题目描述
有一个称为“模拟工厂”的游戏是这样的:在时刻 $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
11
说明
**【数据范围】**
| 编号 | $n \le$ | $t_i \le$ | $g_i \le$ | $m_i \le$ |
|:-:|:-:|:-:|:-:|:-:|
| $1 \sim 3$ | $5$ | $100$ | $10000$ | $10000$ |
| $4 \sim 6$ | $10$ | $100$ | $10000$ | $10000$ |
| $7 \sim 10$ | $15$ | $100000$ | $10^9$ | $10^9$ |