Initially, Snuke can’t move at all. There are $n$ tickets, and the price of the $i$-th ticket is $p_i$. If Snuke buys the $i$-th ticket, for all points $(x, y)$ and a nonnegative number $t$, he can move from $(x, y)$ to $(x + ta_i, y + tb_i)$. Snuke wants to buy tickets and he wants to be able to travel between any two points. Compute the minimal possible total price of the tickets he must buy.

Input

First line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$). Then $n$ lines follow; $i$’th of these lines contains three integers $a_i$, $b_i$, $p_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le p_i \le 10^9$).

Output

Print the minimal possible total price of the tickets he must buy in order to be able to move between any two points. If this is impossible, print $-1$ instead.

Examples

Input 1

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

Output 1

4

Input 2

2
1 2 3
4 5 6

Output 2

-1

Note

In the Sample 1 you can, for example, buy tickets 1, 3, 6.