A properly designed room is, as we all know, well-lit.

In keeping with the teachings of Feng Shui, you have placed a number of lamps around a newly-designed room at strategic places to give it a friendlier air.

Some of the lights project positive energy, and the rest give out only negative energy. Luckily, your neighbourhood guru knows all about this, and will gladly help you to keep the delicate energy balance…For a small fee.

The balancing line of a particular lighting arrangement is the shortest continuous closed circuit dividing energy sources into two parts, those inside the line and those outside the line, such that the sum of energies inside and outside is equal—cancelling out any negative effects.

What is the length of this line?

-----Input-----
 - A line with one positive integer, $N$ ($2 \le N \le 12$), the number of lamps.
 - $N$ more lines, each containing three space-separated integers $x_{i}$ and $y_{i}$ ($1 \leq x_{i}, y_{i} \leq 99$) giving the coordinates of the $i$-th lamp expressed in centimetres from the corner of the room, and $e_ i$ ($-2000 \le e_ i \le 2000$), the energy contribution of this lamp. A lamp placed at ($x, y$) has a square footprint that fits inside the square with opposite corners ($x-1, y-1$) and ($x+1, y+1$) with a tiny amount of space to spare.

It is guaranteed that no two lamps will have overlapping footprints.

-----Output-----
Write one real number: the length of the shortest continuous line dividing the positive and negative energy sources in the room. Your answer should be correct up to an absolute or relative precision of $10^{-6}$.

If no such line exists, output IMPOSSIBLE instead.

-----Examples-----
Sample Input 1:
4
10 10 5
10 20 5
20 10 5
20 20 5
Sample Output 1:
28

Sample Input 2:
4
10 10 5
10 20 1
20 10 12
20 20 8
Sample Output 2:
36.2842712475

Sample Input 3:
6
1 1 15
5 1 100
9 1 56
1 5 1
5 5 33
9 5 3
Sample Output 3:
28.970562748

Sample Input 4:
8
4 4 1
4 6 1
4 8 1
6 6 14
8 4 1
8 6 1
8 8 1
99 6 -8
Sample Output 4:
32

Source: kattis | Difficulty: HARD


Solutions: