购买游戏机

题目描述

高桥君打算购买人气游戏机「スヌケマシン」。

销售スヌケマシン的店铺有店 $1, 2, \dots, N$ 共 $N$ 家,从高桥君的当前位置步行到店 $i$ 需要 $A_i$ 分钟,スヌケマシン的售价为 $P_i$ 日元,当前スヌケマシンの库存为 $X_i$ 台。

高桥君从现在开始步行前往销售スヌケマシン的店铺,到达店铺时如果スヌケマシン有库存就购买。

但是,スヌケマシン是人气商品,从现在起每经过 $0.5, 1.5, 2.5, \dots$ 分钟,所有店铺的スヌケマシン库存(如果存在)都会减少 $1$ 台。

请判断高桥君能否买到スヌケマシン,如果能买到,请求出所需的最小金额。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $P_1$ $X_1$
$\vdots$
$A_N$ $P_N$ $X_N$

输出格式

如果高桥君能买到スヌケマシン,输出所需的最小金额。

如果不能买到,输出 -1。

样例

3
3 9 5
4 8 5
5 7 5

8

去店 $1$ 时,高桥君到达时スヌケマシン还剩 $2$ 台,可以用 $9$ 日元买到スヌケマシン。

去店 $2$ 时,高桥君到达时スヌケマシン还剩 $1$ 台,可以用 $8$ 日元买到スヌケマシン。

去店 $3$ 时,高桥君到达时スヌケマシン已经卖完,买不到。

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 \le N \le 10^5$
• $1 \le A_i, P_i, X_i \le 10^9$