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

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

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.

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_{i} denotes 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.

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

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

提交代码