/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 200 点
問題文
高橋くんは人気ゲーム機「スヌケマシン」を買おうとしています。
スヌケマシンを販売している店は店 1, 2, \dots, N の N 軒あり、店 i は高橋くんの現在地から徒歩 A_i 分、スヌケマシンの販売価格は P_i 円、現在のスヌケマシンの在庫は X_i 台です。
高橋くんは今から徒歩でスヌケマシンを販売している店に向かい、店に着いたときにスヌケマシンの在庫があればスヌケマシンを買います。
しかし、スヌケマシンは人気商品なので、今から 0.5, 1.5, 2.5, \dots 分後に全ての店でスヌケマシンの在庫が (存在するなら) 1 台減ります。
高橋くんがスヌケマシンを買うことができるか判定し、できる場合は買うのに必要な最小の金額を求めてください。
制約
- 入力は全て整数
- 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
出力
高橋くんがスヌケマシンを買うことができる場合は、買うのに必要な最小の金額を出力せよ。
できない場合は、-1 を出力せよ。
入力例 1
3 3 9 5 4 8 5 5 7 5
出力例 1
8
店 1 に向かうと、高橋くんが着いたときにはスヌケマシンが 2 台残っていて、9 円でスヌケマシンを買うことができます。
店 2 に向かうと、高橋くんが着いたときにはスヌケマシンが 1 台残っていて、8 円でスヌケマシンを買うことができます。
店 3 に向かうと、高橋くんが着いたときにはスヌケマシンが売り切れていて、買うことができません。
入力例 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
Score : 200 points
Problem Statement
Takahashi wants to buy the popular video game console called Play Snuke.
There are N shops that sell Play Snuke: Shop 1, 2, \dots, N. Shop i is A_i minutes' walk from where Takahashi is now, sells Play Snuke for P_i yen (Japanese currency), and currently has X_i Play Snukes in stock.
Now, Takahashi will go to one of those shops on foot and buy Play Snuke if it is still in stock when he gets there.
However, Play Snuke is so popular that the number of consoles in stock (if any) in every shop will decrease by 1 at the following moments: 0.5, 1.5, 2.5, \dots minutes from now.
Determine whether Takahashi can buy Play Snuke. If he can, find the minimum amount of money needed to buy one.
Constraints
- All values in input are integers.
- 1 ≤ N ≤ 10^5
- 1 ≤ A_i, P_i, X_i ≤ 10^9
Input
Input is given from Standard Input in the following format:
N A_1 P_1 X_1 \vdots A_N P_N X_N
Output
If Takahashi can buy Play Snuke, print the minimum amount of money needed to buy one, as an integer.
If he cannot buy one, print -1.
Sample Input 1
3 3 9 5 4 8 5 5 7 5
Sample Output 1
8
If he goes to Shop 1, it will still have 2 Play Snukes when he gets there, and he can buy one for 9 yen.
If he goes to Shop 2, it will still have 1 Play Snuke when he gets there, and he can buy one for 8 yen.
If he goes to Shop 3, Play Snuke will be out of stock when he gets there; he cannot buy one.
Sample Input 2
3 5 9 5 6 8 5 7 7 5
Sample Output 2
-1
Sample Input 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
Sample Output 3
861648772