すぬけ君は，初期状態では動くことはできない．i 番目のチケットの値段は p_i であり，これを買うと任意の (x, y) と任意の非負実数 t に対し(x, y) から(x + ta_i, y + tb_i) に移動することができるようになる．すぬけ君が平面上の任意の二点間を(いくつかのチケットを組み合わせて) 移動できるようになるために買わなければならないチケットの合計金額の最小値を求めよ．

Constraints

• 1 ≤ n ≤ 200000
• −10⁹ ≤ a_i, b_i ≤ 10⁹
• 1 ≤ p_i ≤ 10⁹
• 入力は全て整数である

Input

n
a1 b1 p1
. . .
an bn pn

Output

平面上の任意の二点間を移動できるようになるために買わなければならないチケットの合計金額の最小値を出力せよ．できない場合は-1 を出力せよ．

Sample Input 1

7
0 3 1
0 3 2
1 -1 2
0 0 1
-2 4 1
-4 0 1
2 1 2

たとえばチケット1, 3, 6 を買うとよい．

Sample Output 1

4

Sample Input 2

2
1 2 3
4 5 6

Sample Output 2

-1

---