AT_abc193_b [ABC193B] Play Snuke

题目描述

高桥君想要购买一台热门游戏机“スヌケマシン”。
有 $N$ 家店铺在售卖スヌケマシン，第 $i$ 家店距离高桥君当前位置步行需要 $A_i$ 分钟，スヌケマシン的售价为 $P_i$ 日元，目前该店的库存为 $X_i$ 台。
高桥君现在可以步行前往任意一家售卖スヌケマシン的店铺，如果到达时店内还有库存，他就会购买一台。
然而，由于スヌケマシン非常受欢迎，从现在开始每过 $0.5, 1.5, 2.5, \dots$ 分钟，每家店（如果有库存）库存会减少 $1$ 台。
请判断高桥君是否能够买到スヌケマシン，如果可以，输出他能买到的最低价格；如果不能，输出 $-1$。

输入格式

输入通过标准输入给出，格式如下：

$N$
$A_1\ P_1\ X_1$
$A_2\ P_2\ X_2$
$\vdots$
$A_N\ P_N\ X_N$

输出格式

如果高桥君能够买到スヌケマシン，输出他能买到的最低价格。
如果不能买到，输出 $-1$。

输入输出样例 #1

输入 #1

3
3 9 5
4 8 5
5 7 5

输出 #1

8

输入输出样例 #2

输入 #2

3
5 9 5
6 8 5
7 7 5

输出 #2

-1

输入输出样例 #3

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

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 10^5$
• $1 \leq A_i, P_i, X_i \leq 10^9$

样例解释 1

如果前往第 $1$ 家店，高桥君到达时スヌケマシン还剩 $2$ 台，可以以 $9$ 日元购买。
如果前往第 $2$ 家店，到达时スヌケマシン还剩 $1$ 台，可以以 $8$ 日元购买。
如果前往第 $3$ 家店，到达时スヌケマシン已经售罄，无法购买。

由 ChatGPT 4.1 翻译