← 返回题目列表

AtCoder · abc193_b

B. 玩 Snuke

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

分数: 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