Początkowo Snuke w ogóle nie może się poruszać. Jest $n$ biletów, a cena $i$-tego biletu wynosi $p_i$. Jeśli Snuke kupi $i$-ty bilet, to dla wszystkich punktów $(x, y)$ i nieujemnej liczby $t$ może przemieścić się z $(x, y)$ do $(x + ta_i, y + tb_i)$. Snuke chce kupić bilety tak, aby móc podróżować między dowolnymi dwoma punktami. Oblicz najmniejszą możliwą łączną cenę biletów, które musi kupić.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 2 \cdot 10^5$). Następnie występuje $n$ wierszy; $i$-ty z nich zawiera trzy liczby całkowite $a_i$, $b_i$, $p_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le p_i \le 10^9$).

Wyjście

Wypisz najmniejszą możliwą łączną cenę biletów, które musi kupić, aby móc poruszać się między dowolnymi dwoma punktami. Jeśli jest to niemożliwe, wypisz zamiast tego $-1$.

Przykład

Wejście 1

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

Wyjście 1

4

Wejście 2

2
1 2 3
4 5 6

Wyjście 2

-1

Uwagi

W przykładzie 1 można na przykład kupić bilety 1, 3, 6.