CF1107F Vasya and Endless Credits

Vasya 想给自己买一辆漂亮的新车。不幸的是，他手头缺钱。目前他正好有 $0$ 布尔。 然而，当地银行有 $n$ 个信贷产品。每个产品可以用三个数字 $a_i$、$b_i$ 和 $k_i$ 来描述。产品编号从 $1$ 到 $n$。如果 Vasya 选择第 $i$ 个产品，那么银行会在本月初给他 $a_i$ 布尔，然后在接下来的 $k_i$ 个月（包括激活该产品的当月）里，每个月月底 Vasya 都要向银行支付 $b_i$ 布尔。Vasya 可以按任意顺序选择这些信贷产品。 每个月 Vasya 最多只能选择一个信贷产品。每个信贷产品也只能使用一次。多个信贷产品可以同时处于激活状态。这意味着，每个月底 Vasya 需要向银行支付所有处于激活状态的信贷产品的 $b_i$ 之和。 Vasya 想在某个月的中旬买车。他会把自己当前拥有的所有钱拿出来，买一辆正好这个价格的车。 Vasya 并不关心买车后还要还银行多少钱。他会开着车离开这个国家，这样银行就再也找不到他了。 请问，这辆车的最大价格是多少？

第一行包含一个整数 $n$（$1 \le n \le 500$），表示信贷产品的数量。 接下来的 $n$ 行，每行包含三个整数 $a_i$、$b_i$ 和 $k_i$（$1 \le a_i, b_i, k_i \le 10^9$）。

输出一个整数，表示这辆车的最大价格。

在第一个样例中，最优的信贷产品选择顺序为：4 $\rightarrow$ 3。 Vasya 拥有的布尔数变化如下：5 $\rightarrow$ 32 $\rightarrow$ -86 $\rightarrow$ ...。他在第二个月的中旬拥有 32 布尔，买下了汽车。 负数表示 Vasya 欠银行的钱。 在第二个样例中，最优的信贷产品选择顺序为：3 $\rightarrow$ 1 $\rightarrow$ 2。 Vasya 拥有的布尔数变化如下：0 $\rightarrow$ 300 $\rightarrow$ 338 $\rightarrow$ 1337 $\rightarrow$ 236 $\rightarrow$ -866 $\rightarrow$ ...。 由 ChatGPT 4.1 翻译