Ban đầu, Snuke hoàn toàn không thể di chuyển. Có $n$ vé, và giá của vé thứ $i$ là $p_i$. Nếu Snuke mua vé thứ $i$, thì với mọi điểm $(x, y)$ và số không âm $t$, cậu có thể di chuyển từ $(x, y)$ đến $(x + ta_i, y + tb_i)$. Snuke muốn mua vé để có thể đi lại giữa hai điểm bất kỳ. Hãy tính tổng giá nhỏ nhất có thể của các vé mà cậu phải mua.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$ ($1 \le n \le 2 \cdot 10^5$). Tiếp theo là $n$ dòng; dòng thứ $i$ trong số đó chứa ba số nguyên $a_i$, $b_i$, $p_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le p_i \le 10^9$).

Dữ liệu ra

In ra tổng giá nhỏ nhất có thể của các vé mà cậu phải mua để có thể di chuyển giữa hai điểm bất kỳ. Nếu điều này không thể thực hiện, hãy in $-1$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

4

Dữ liệu vào 2

2
1 2 3
4 5 6

Dữ liệu ra 2

-1

Ghi chú

Trong ví dụ 1, chẳng hạn, bạn có thể mua các vé 1, 3, 6.