2434: Defence of the Trees

There are n trees (each of them can be considered as a point) on a two-dimensional coordinate system. There are k categories of trees, category of the i^th tree are represented by A_i. There are also m stumps (each of them can be considered as a point, too) on this two-dimensional coordinate system. Stumps can be connected with straight wires.

Your task is to connect some of the stumps by wires to build exactly one simple polygon (that is, a polygon without self-intersection and degeneration) which contains trees of all k categories inside. Meanwhile, in order to save money, you should make the total length of wires as short as possible. Your task is to calculate the shortest total length of wires, or to determine that there is no solutions.

There are several testcases, please process till EOF.

In each testcases:
First one line, three numbers n, m, k. Following n lines contains n 2D-coordinates describing each tree. Next one line contains n number, where i^th number A_idenotes i^th tree's category. Next m lines describe the coordinates of stumps, you may assume that there is no trees lying on segments between any two stumps.

All input will be integer, and absolute value of them will be less than 23333, 1 ≤ n ≤ 300, 1 ≤ m ≤ 40, 1 ≤ k ≤ 6,1 ≤ A_i ≤ k.In about 90% of testcases,m ≤ 10.

For each testcase, print one line, if there is no solutions, Output "Impossible" (without quotes), else output a real number indicating the minimal total length. Your answer will be considered correct if and only if the absolute error or relative error are less than 10^-6.

2 4 1  
0 0  
2 0  
1 1  
1 -1  
1 1  
-3 -1  
5 1  
2 4 2  
0 0  
2 0  
1 2  
1 -1  
1 1  
-3 -1  
5 1 

10.472135955000  
16.944271909999