Directions

Sunuke cannot move in the initial state. The price of the i-th ticket is pi, which can be bought to move from (x, y) to (x + tai, y + tbi) for any (x, y) and any non-negative real number t. become able to. Find the minimum total amount of tickets that Sunuke must buy in order to be able to move between any two points on the plane (combining several tickets).

Constraints

• 1 ≤ n ≤ 200000
• −109 ≤ ai, bi ≤ 109
• 1 ≤ pi ≤ 109
• All inputs are integers

Input

n a1 b1 p1 .. .. an bn pn

Output

Output the minimum total amount of tickets you must buy to be able to move between any two points on the plane. If not, output -1.

Examples

Input

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

Output

4

Input

2 1 2 3 4 5 6

Output

-1

inputFormat

inputs are integers

Input

n a1 b1 p1 .. .. an bn pn

outputFormat

Output

Output the minimum total amount of tickets you must buy to be able to move between any two points on the plane. If not, output -1.

Examples

Input

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

Output

4

Input

2 1 2 3 4 5 6

Output

-1

样例

2
1 2 3
4 5 6

-1