Defence of the Trees

Time Limit: 20000/10000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

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 ith tree are represented by Ai. 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.

Input

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 ith number Ai denotes ith 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 ≤ Ai ≤ k.In about 90% of testcases,m ≤ 10.

Output

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.

Sample Input

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

Sample Output

10.472135955000 16.944271909999

Hint

Source

2014 Multi-University Training Contest 3

提交代码