题目描述

有一个称为“模拟工厂”的游戏是这样的：在时刻 $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$ 位带符号整数范围内。

2
5 1 8
7 15 3

11

提示

【数据范围】