最初、Snuke はまったく移動できません。$n$ 枚のチケットがあり、$i$ 番目のチケットの価格は $p_i$ です。Snuke が $i$ 番目のチケットを購入すると、すべての点 $(x, y)$ と非負の数 $t$ に対し、$(x, y)$ から $(x + ta_i, y + tb_i)$ へ移動できます。Snuke はチケットを購入して、任意の 2 点間を移動できるようにしたいと考えています。購入しなければならないチケットの合計価格の最小値を求めてください。

入力

入力の最初の行には整数 $n$（$1 \le n \le 2 \cdot 10^5$）が与えられます。続いて $n$ 行が与えられ、そのうち $i$ 行目には 3 つの整数 $a_i$, $b_i$, $p_i$（$-10^9 \le a_i, b_i \le 10^9$, $1 \le p_i \le 10^9$）が含まれます。

出力

任意の 2 点間を移動できるようにするために購入しなければならないチケットの合計価格の最小値を出力してください。不可能な場合は、代わりに $-1$ を出力してください。

入出力例

入力 1

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

出力 1

4

入力 2

2
1 2 3
4 5 6

出力 2

-1

注記

入出力例 1 では、例えばチケット 1, 3, 6 を購入できます。