Awalnya, Snuke sama sekali tidak dapat bergerak. Terdapat $n$ tiket, dan harga tiket ke-$i$ adalah $p_i$. Jika Snuke membeli tiket ke-$i$, untuk semua titik $(x, y)$ dan bilangan tak negatif $t$, ia dapat bergerak dari $(x, y)$ ke $(x + ta_i, y + tb_i)$. Snuke ingin membeli tiket agar ia dapat bepergian antara sembarang dua titik. Hitung harga total minimum yang mungkin untuk tiket-tiket yang harus ia beli.

Masukan

Baris pertama masukan berisi satu bilangan bulat $n$ ($1 \le n \le 2 \cdot 10^5$). Kemudian terdapat $n$ baris; baris ke-$i$ di antaranya berisi tiga bilangan bulat $a_i$, $b_i$, $p_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le p_i \le 10^9$).

Keluaran

Cetak harga total minimum yang mungkin untuk tiket-tiket yang harus ia beli agar dapat bergerak antara sembarang dua titik. Jika ini tidak mungkin, cetak $-1$ sebagai gantinya.

Contoh

Masukan 1

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

Keluaran 1

4

Masukan 2

2
1 2 3
4 5 6

Keluaran 2

-1

Catatan

Pada contoh 1, misalnya, Anda dapat membeli tiket 1, 3, 6.