130 - ZOJ Monthly, January 2014 - J
As the only oni (a kind of fabulous creature with incredible strength and power) currently living on the surface of Gensokyo, Ibuki Suika started to lodge at the Hakurei Shrine due to some events. The current miko (means shrine maiden or priestess) in the shrine is Hakurei Reimu, who is known as the laziest miko during the history of Gensokyo.
Being the miko of Hakurei Shrine, Reimu manages the Hakurei Border of Gensokyo and often goes out to exterminate troublemakers. However, after Suika came to live, Reimu's nature of laziness was exposed and she often asks Suika to finish missions instead of her.
One day, Suika is flying in the Bamboo Forest of the Lost, and she finds herself surrounded by N monsters which look like white balls of fur. The monsters are called Kedamas. For the i-th Kedama, Suika needs to consume Ai units of power to wipe it out. Of course, Suika can easily exterminate all of them, but it is a waste of power. Nevertheless, she finds that there are M useful items, which can help her restore the power. For the i-th item, if Suika gets it, she will restore Bi units of power. So Suika decides to eliminate some of the Kedamas, collect the items and maximize her power in the end.
The Bamboo Forest of the Lost can be regarded as a two-dimensional plane, and Suika can be considered as a point at (0,0). The Kedamas can be regarded as convex polygons, and it is assured that they would not intersect or overlap with each other. The items also can be regarded as points on the plane. Different items may have same coordinates. Neither Suika nor the items will locate inside any Kedamas or on the boundaries of them. No items will appear at (0,0).
If the segment between an item and Suika does not intersect with any Kedamas, she can get the item directly. Otherwise, she need to attack some Kedamas to clear out a way to get the item. If the segment between Suika and any points of a Kedama does not intersect with other Kedamas, she can spend power to exterminate it.
Suika was a little drunk, so she found it difficult to quickly and precisely calculate the maximal power she will get. Please help her to calculate it.
There are multiple test cases (no more than 100). For each test case:
The first line contains two integers N and M (1 <= N, M <= 400). The next line contains N integers Ai and the following line contains M integers Bi (1 <= Ai, Bi <= 1000).
Then followed by N lines. Each lines starts with a integer Ci (1 <= Ci <= 20), indicates the number of edges of the i-th Kedama. Following 2 * Ci real numbers indicates the coordinate of the j-th vertex, in the format of Xi1 Yi1 Xi2 Yi2 .. XiCi YiCi. The vertices are given in clockwise order.
The last M lines, each line contains two real numbers representing the coordinate of the i-th item. The absolute value of all real numbers will be no more than 1000.
For each test case, output the maximal power Suika could get.
2 1 3 4 5 4 1.0 1.0 1.0 2.0 2.0 2.0 2.0 1.0 4 -1.0 -1.0 -2.0 -1.0 -2.0 -2.0 -1.0 -2.0 3.0 3.0
Author: WANG, Xiajun