最初，Snuke 完全郁唔到。有 $n$ 張票，第 $i$ 張票嘅價錢係 $p_i$。如果 Snuke 買咗第 $i$ 張票，咁對所有點 $(x, y)$ 同非負數 $t$，佢都可以由 $(x, y)$ 移動到 $(x + ta_i, y + tb_i)$。Snuke 想買啲票，令自己可以喺任意兩點之間來往。計算佢要買嘅票嘅最低總價。

輸入格式

輸入第一行有一個整數 $n$（$1 \le n \le 2 \cdot 10^5$）。之後有 $n$ 行，第 $i$ 行有三個整數 $a_i$、$b_i$、$p_i$（$-10^9 \le a_i, b_i \le 10^9$，$1 \le p_i \le 10^9$）。

輸出格式

輸出為咗可以喺任意兩點之間移動，佢要買嘅票嘅最低總價。如果做唔到，就輸出 $-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 張票。