Play Snuke

题目描述

Takahashi 想要购买名为 Play Snuke 的热门游戏机。
有 $N$ 家商店出售 Play Snuke：商店 $1, 2, \dots, N$。商店 $i$ 距离 Takahashi 当前位置步行需要 $A_i$ 分钟，出售 Play Snuke 的价格为 $P_i$ 日元，并且当前库存为 $X_i$ 台 Play Snuke。
现在，Takahashi 将步行前往其中的一家商店，如果他到达时该商店仍有库存就购买一台。
然而，Play Snuke 如此受欢迎，以至于每家商店的库存（如果有的话）会在以下时刻减少 $1$ 台：$0.5, 1.5, 2.5, \dots$ 分钟之后。
判断 Takahashi 是否能买到 Play Snuke。如果能，求买到一台所需的最少金额。

输入格式

从标准输入给出如下格式的输入： $N$ $A_1$ $P_1$ $X_1$ $\vdots$ $A_N$ $P_N$ $X_N$

输出格式

如果 Takahashi 能买到 Play Snuke，打印买到一台所需的最少金额，作为一个整数。
如果他买不到一台，打印 $-1$。

3
3 9 5
4 8 5
5 7 5

8

3
5 9 5
6 8 5
7 7 5

-1

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

861648772

提示

输入中的所有数值均为整数。 $1 ≤ N ≤ 10^5$ $1 ≤ A_i, P_i, X_i ≤ 10^9$如果他去商店 $1$，当他到达时仍会有 $2$ 台 Play Snuke，他可以用 $9$ 日元买到一台。
如果他去商店 $2$，当他到达时仍会有 $1$ 台 Play Snuke，他可以用 $8$ 日元买到一台。
如果他去商店 $3$，当他到达时 Play Snuke 将售罄；他无法买到一台。

标签: AtCoder|abc193B

来源

AtCoder|abc193B