Anfangs kann sich Snuke überhaupt nicht bewegen. Es gibt $n$ Fahrkarten, und der Preis der $i$-ten Fahrkarte ist $p_i$. Wenn Snuke die $i$-te Fahrkarte kauft, kann er sich für alle Punkte $(x, y)$ und eine nichtnegative Zahl $t$ von $(x, y)$ nach $(x + ta_i, y + tb_i)$ bewegen. Snuke möchte Fahrkarten kaufen und zwischen beliebigen zwei Punkten reisen können. Berechne den kleinstmöglichen Gesamtpreis der Fahrkarten, die er kaufen muss.

Eingabe

Die erste Eingabezeile enthält eine ganze Zahl $n$ ($1 \le n \le 2 \cdot 10^5$). Danach folgen $n$ Zeilen; die $i$-te davon enthält drei ganze Zahlen $a_i$, $b_i$, $p_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le p_i \le 10^9$).

Ausgabe

Gib den kleinstmöglichen Gesamtpreis der Fahrkarten aus, die er kaufen muss, um sich zwischen beliebigen zwei Punkten bewegen zu können. Falls dies unmöglich ist, gib stattdessen $-1$ aus.

Beispiele

Eingabe 1

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

Ausgabe 1

4

Eingabe 2

2
1 2 3
4 5 6

Ausgabe 2

-1

Hinweis

Im Beispiel 1 kann man zum Beispiel die Fahrkarten 1, 3, 6 kaufen.