B - 玩Snuke

分数：200分

问题描述

Takahashi想要买一台名叫Play Snuke的流行的游戏机。
有$N$个商店出售Play Snuke：商店$1, 2, \dots, N$。商店$i$离Takahashi现在所在的地方有$A_i$分钟的步行路程，出售价格为$P_i$日元，目前库存有$X_i$台Play Snuke。
现在，Takahashi将步行前往这些商店之一，并在到达商店后购买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。

3
3 9 5
4 8 5
5 7 5

8

如果他去商店$1$，当他到达时还有$2$台Play Snukes，他可以以$9$日元购买一台。
如果他去商店$2$，当他到达时还有$1$台Play Snukes，他可以以$8$日元购买一台。
如果他去商店$3$，当他到达时Play Snukes已经售罄，他无法购买。

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