题目描述

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。

示例输入 1

3
3 9 5
4 8 5
5 7 5

示例输出 1

8

如果他去店铺 $1$，当他到达时，它将还有 $2$ 台 Play Snuke，并且他可以用 9 日元购买一台。
如果他去店铺 $2$，当他到达时，它将还有 $1$ 台 Play Snuke，并且他可以用 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