起初，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 張票。