← 返回题目列表

Codeforces · 1107/F

F. Vasya 和无尽的积分

中文机器翻译题面 查看原题

Vasya 想给自己买一辆漂亮的新车。不幸的是,他缺一些钱。目前他的 burles 正好为 0。

但是,当地银行有 $$$n$$$ 信贷优惠。每个优惠都可以用三个数字 $$$a_i$$$、$$$b_i$$$ 和 $$$k_i$$$ 来描述。优惠编号从 $$$1$$$ 到 $$$n$$$。如果 Vasya 接受了第 $$$i$$$ 个报价,那么银行会在月初向他支付 $$$a_i$$$ burles,然后 Vasya 在接下来的 $$$k_i$$$ 个月(包括他激活报价的月份)的每月月底向银行支付 $$$b_i$$$ burles。 Vasya 可以接受他想要的任何订单。

每个月 Vasya 只能接受一项信用优惠。此外,每个信用优惠不能多次使用。多个积分可以同时激活。这意味着 Vasya 在每个月末向银行支付所有 $$$i$$$ 活跃信用的 $$$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$$$)。

输出

打印一个整数——汽车的最高价格。

示例

输入 #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

注意

在第一个示例中,以下报价顺序是最佳的:4 $$$\rightarrow$$$ 3.

burles Vasya 的数量发生了以下变化: 5 $$$\rightarrow$$$ 32 $$$\rightarrow$$$ -86 $$$\rightarrow$$$ .... 他在第二个月中旬拿出了他的钱(32 burles)并购买了汽车。

负金额意味着 Vasya 必须向银行支付该金额的 burles。

在第二个示例中,以下报价顺序是最佳的:3 $$$\rightarrow$$$ 1 $$$\rightarrow$$$ 2。

burles Vasya 的数量发生以下变化: 0 $$$\rightarrow$$$ 300 $$$\rightarrow$$$ 338 $$$\rightarrow$$$ 1337 $$$\rightarrow$$$ 236 $$$\rightarrow$$$ -866 $$$\rightarrow$$$ ....