Problem E
Grand Combat Doctrine

Two commanders clash for dominance over an infinite two-dimensional battlefield. To seize full control, an army must be capable of constructing military roads in every direction. However, building that capability comes at a cost.

There are $N$ available engineering doctrines. Doctrine $i$ teaches engineers to construct roads along the direction $(x_i, y_i)$ and costs $c_i$ to learn. Once learned, a doctrine allows roads to be built outward in that direction from anywhere, or backward along the opposite direction for any length.

When multiple doctrines are learned, say $(x_1, y_1)$ and $(x_2, y_2)$, then the engineers can learn (for 0 cost) how to build a road in any direction of the form $(a \cdot x_1 + b \cdot x_2, a \cdot y_1 + b \cdot y_2), \forall a, b \in \mathbb {R}$. To guarantee total battlefield coverage, a commander must be able to reach every point on the plane through such combinations.

Determine the minimum total cost to learn a set of doctrines that achieves full battlefield coverage. If it is impossible, output IMPOSSIBLE.

Input

The first line contains an integer $N$ ($1 \le N \le 2 \cdot 10^5$), the number of available doctrines.

Each of the next $N$ lines contains three integers:

• $c_i$ ($1 \le c_i \le 10^6$), the price of the $i_{th}$ training doctrine.

• $x_i$ ($-10^6 < x_i < 10^6)$, the $x$-coordinate that the $i_{th}$ training doctrine can reach.

• $y_i$ ($-10^6 < y_i < 10^6)$, the $y$-coordinate that the $i_{th}$ training doctrine can reach.

It is guaranteed that $(x_i, y_i) \ne (0,0)$.

Output

Output a single line containing:

• the minimum total cost required to reach every point on the plane, or

• IMPOSSIBLE if it is impossible to learn how to reach every point on the plane.

4
10 1 1
5 -3 -3
5 -1 10
10 1 -10

10

3
10 1 1
5 -3 -3
20 4 4

IMPOSSIBLE