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$$$ ....