无尽信贷

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

Vasya 最初没有钱。银行提供 $n$ 个互不相同的信贷产品，第 $i$ 个产品由 $a_i,b_i,k_i$ 描述：选择它时，银行会在当月月初给 Vasya $a_i$ 布尔；从当月起连续 $k_i$ 个月，每个月月底 Vasya 都要偿还 $b_i$ 布尔。

每个月至多选择一个产品，每个产品至多选择一次，多个产品可以同时处于还款期。Vasya 可以在某个月的月中、也就是收到当月选择的产品款项之后且支付当月还款之前，用当时所有的钱买车。买车之后的债务无需考虑。

求车价的最大可能值。允许只选择一部分产品。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行三个整数 $a_i,b_i,k_i$。

输出格式

输出最大车价。

样例输入 1

4
10 9 2
20 33 1
30 115 1
5 3 2

样例输出 1

32

样例输入 2

3
40 1 2
1000 1100 5
300 2 1

样例输出 2

1337

数据范围

• $1\le n\le500$；
• $1\le a_i,b_i,k_i\le10^9$。

计分方式

本题按测试点独立计分，同一子任务中的测试点等分。