问题标题: 酷町堂：3244 坦克生产

3244   坦克生产

题目描述 Description

在某国即将发动对另一个国家的战争之前，该国的某个军工厂正在疯狂的加紧生产坦克，假设该军工厂在0时刻初始的生产力为1，接下来的每一个时刻，工厂老板可以选择提高生产力或者继续生产坦克，如果选择提高生产力，那么下一个时刻该军工厂的生产力加1；如果选择生产坦克，则下一个时刻工厂所拥有的坦克数量增加p，其中p是本时刻工厂的生产力。现在有来自于政府的n个订单，可以选择接受或者不接受。第i个订单(ti, gi, mi)要求在时刻ti给政府提供gi辆坦克，事成之后坦克数量减少gi，而工厂的收入增加mi元。如果接受订单i，则必须恰好在时刻ti交易，不能早也不能晚。同一时刻可以接受多个订单，但每个订单只能被接受一次。要求最后的总收入最大。例如，如果一共有两个订单(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。

输入描述 Input Description

输入第一行包含一个整数n，即订单数目。以下n行每行三个整数ti, gi, mi。

输出描述 Output Description

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

样例输入 Sample Input

2
5 1 8
7 15 3

样例输出 Sample Output

11

数据范围及提示 Data Size & Hint

1≤n≤100;
0≤ ti, gi, mi ≤1000000;