[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$ ，表示第 $i$ 个订单要求在时刻 $t_i$ 提供 $g_i$ 个商品，完成后可获得 $m_i$ 元收入。

输出格式

输出一行一个整数，表示可以获得的最大总收入。

答案保证在 $32$ 位有符号整数范围内。

样例输入

2
5 1 8
7 15 3

样例输出

数据范围

对于编号为 $1\sim 3$ 的测试点， $n\le 5$ ， $t_i\le 100$ ， $g_i\le 10^4$ ， $m_i\le 10^4$ ；
对于编号为 $4\sim 6$ 的测试点， $n\le 10$ ， $t_i\le 100$ ， $g_i\le 10^4$ ， $m_i\le 10^4$ ；
对于编号为 $7\sim 10$ 的测试点， $n\le 15$ ， $t_i\le 10^5$ ， $g_i\le 10^9$ ， $m_i\le 10^9$ 。

来源与许可

本题为 CQOI 2012 试题「模拟工厂」，题面与测试数据整理自 BZOJ 2667。

样例 1

输入

2
5 1 8
7 15 3