{"raw_statement":[{"iden":"problem statement","content":"Takahashi wants to buy the popular video game console called Play Snuke.  \nThere 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.  \nNow, Takahashi will go to one of those shops on foot and buy Play Snuke if it is still in stock when he gets there.  \nHowever, 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.  \nDetermine whether Takahashi can buy Play Snuke. If he can, find the minimum amount of money needed to buy one."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 ≤ N ≤ 10^5$\n*   $1 ≤ A_i, P_i, X_i ≤ 10^9$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $P_1$ $X_1$\n$\\vdots$\n$A_N$ $P_N$ $X_N$"},{"iden":"sample input 1","content":"3\n3 9 5\n4 8 5\n5 7 5"},{"iden":"sample output 1","content":"8\n\nIf he goes to Shop $1$, it will still have $2$ Play Snukes when he gets there, and he can buy one for $9$ yen.  \nIf he goes to Shop $2$, it will still have $1$ Play Snuke when he gets there, and he can buy one for $8$ yen.  \nIf he goes to Shop $3$, Play Snuke will be out of stock when he gets there; he cannot buy one."},{"iden":"sample input 2","content":"3\n5 9 5\n6 8 5\n7 7 5"},{"iden":"sample output 2","content":"\\-1"},{"iden":"sample input 3","content":"10\n158260522 877914575 602436426\n24979445 861648772 623690081\n433933447 476190629 262703497\n211047202 971407775 628894325\n731963982 822804784 450968417\n430302156 982631932 161735902\n880895728 923078537 707723857\n189330739 910286918 802329211\n404539679 303238506 317063340\n492686568 773361868 125660016"},{"iden":"sample output 3","content":"861648772"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}