Initialement, Snuke ne peut pas du tout se déplacer. Il y a $n$ billets, et le prix du $i$-ème billet est $p_i$. Si Snuke achète le $i$-ème billet, pour tous les points $(x, y)$ et un nombre non négatif $t$, il peut se déplacer de $(x, y)$ à $(x + ta_i, y + tb_i)$. Snuke veut acheter des billets et pouvoir voyager entre deux points quelconques. Calculez le prix total minimal possible des billets qu’il doit acheter.

Entrée

La première ligne de l’entrée contient un entier $n$ ($1 \le n \le 2 \cdot 10^5$). Ensuite viennent $n$ lignes ; la $i$-ème d’entre elles contient trois entiers $a_i$, $b_i$, $p_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le p_i \le 10^9$).

Sortie

Affichez le prix total minimal possible des billets qu’il doit acheter pour pouvoir se déplacer entre deux points quelconques. Si cela est impossible, affichez $-1$ à la place.

Exemples

Entrée 1

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

Sortie 1

4

Entrée 2

2
1 2 3
4 5 6

Sortie 2

-1

Remarque

Dans l’exemple 1, on peut, par exemple, acheter les billets 1, 3, 6.