分数: 200 点
问题陈述
高桥想要购买名为 Play Snuke 的流行视频游戏机。
有 N 出售 Play Snuke 的商店:商店 1, 2, \dots, N。商店 i is A_i 距高桥现在所在位置步行几分钟,Play Snuke 售价为 P_i 日元(日本货币),目前有 X_i 玩库存中的 Snukes。
现在,高桥将步行前往其中一家商店并购买 Play Snuke(如果他到达那里时仍有库存)。
然而,Play Snuke 非常受欢迎,以至于每个商店中的库存游戏机数量(如果有)将减少 1 在以下时刻: 0.5, 1.5, 2.5, \dots 分钟后。
确定 Takahashi 是否可以购买 Play Snuke。如果可以的话,找出购买一件产品所需的最低金额。
约束
- 输入中的所有值都是整数。 您选择的
- 1 ≤ N ≤ 10^5
- 1 ≤ A_i, P_i, X_i ≤ 10^9
输入
输入由标准输入按以下格式给出:
N A_1 P_1 X_1 \vdots A_N P_N X_N
输出
如果 Takahashi 可以购买 Play Snuke,请打印购买一个所需的最低金额(整数)。
如果他买不到,请打印 -1.
示例输入 1
3 3 9 5 4 8 5 5 7 5
示例输出 1
8
如果他去商店 1,它仍然会有 2 当他到达那里时玩 Snukes,他可以花 1 美元购买一个 9 日元。
如果他去商店 2,它仍然会有 1 当他到达那里时玩《Snuke》,他可以花 100 美元购买一个 8 日元。
如果他去商店 3,Play Snuke 到了就会缺货;他买不到。
示例输入 2
3 5 9 5 6 8 5 7 7 5
示例输出 2
-1
示例输入 3
10 158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784 450968417 430302156 982631932 161735902 880895728 923078537 707723857 189330739 910286918 802329211 404539679 303238506 317063340 492686568 773361868 125660016
示例输出 3
861648772