题目描述

高橋くんは人気ゲーム機「スヌケマシン」を買おうとしています。
スヌケマシンを販売している店は店 $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 を出力せよ。

题目大意

高桥君打算买游戏机。现在一共有 $n$ 个店铺卖游戏机。

到达第 $i$ 个店需要 $a_i$ 分钟，该店价格是 $p_i$，库存是 $x_i$。

因为游戏机比较抢手，所以第 $0.5$ 分钟、$1.5$ 分钟、$2.5$ 分钟、$......$，每个店的库存都会减 $1$（如果还有的话）。

请判断高桥君能否买到游戏机，如果能买到，输出他所需要花费的最低金额。否则输出 $-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$

Sample Explanation 1

店 $1$ に向かうと、高橋くんが着いたときにはスヌケマシンが $2$ 台残っていて、$9$ 円でスヌケマシンを買うことができます。 店 $2$ に向かうと、高橋くんが着いたときにはスヌケマシンが $1$ 台残っていて、$8$ 円でスヌケマシンを買うことができます。 店 $3$ に向かうと、高橋くんが着いたときにはスヌケマシンが売り切れていて、買うことができません。