Inicialmente, Snuke no puede moverse en absoluto. Hay $n$ billetes, y el precio del $i$-ésimo billete es $p_i$. Si Snuke compra el $i$-ésimo billete, para todos los puntos $(x, y)$ y un número no negativo $t$, puede moverse de $(x, y)$ a $(x + ta_i, y + tb_i)$. Snuke quiere comprar billetes y poder viajar entre dos puntos cualesquiera. Calcula el mínimo precio total posible de los billetes que debe comprar.

Entrada

La primera línea de la entrada contiene un entero $n$ ($1 \le n \le 2 \cdot 10^5$). A continuación hay $n$ líneas; la $i$-ésima de ellas contiene tres enteros $a_i$, $b_i$, $p_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le p_i \le 10^9$).

Salida

Imprime el mínimo precio total posible de los billetes que debe comprar para poder moverse entre dos puntos cualesquiera. Si es imposible, imprime $-1$ en su lugar.

Ejemplos

Entrada 1

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

Salida 1

4

Entrada 2

2
1 2 3
4 5 6

Salida 2

-1

Nota

En el ejemplo 1 puedes, por ejemplo, comprar los billetes 1, 3, 6.