9396번 - Indisputable Right 다국어

Flatland is a 2-dimensional world in which some creatures have an odd miserable life. Despite the many handicaps, the poor creatures have recently achieved the wireless technology in Flatland. So, the priest circles (governors of Flatland who kill the apostles of 3D as soon as they see one) created the national motto “Wireless technology is our indisputable right!” and organized a wireless spreading committee for connecting
all important points of the Flatland by wireless antennas.

Everything went well until the committee reached the mountainous region of Flatland. This region can be modeled with a horizontal base line covered by a contiguous serie of mountain. Each mountain is a right-angled isosceles triangle with its base on the base line and its right angle as the peak. Currently, there are only two types of mountains in this region: those with a height of 50, and those with a height of 100. You can see a sample of the mountainous region in the figure below.

The wireless spreading comitte first installed their antennas on the points they had already planned for the mountainous region. But in the end, they found out that a pair of antennas could directly communicate only if the line segment connecting the two antennas had no crossing intersection with any obstacles — specifically the mountains here. Note that two antennas can communicate if only the border of obstacles is on their connecting line segment.

Since removing a wireless antenna in Flatland is nowadays as a deadly sin as “chromatization”, the only way to connect the set of already installed antennas is to install some extra antennas on the appropriate points of the mountains! Wireless antennas can generally relay the messages and connect to ones which cannot communicate directly. In order to reduce the expenses of installing extra antennas, the wireless spreading committee has hired you to find the minimum number of antennas needed to install.

For example, consider the 4 diamond-shaped points in the figure below as the place of the wireless antennas already installed on the mountains. Now the whole set becomes connected if you instal 3 new antennas in the places specified by the circle-shaped points.

There are multiple test cases in the input. Each test case starts with a line containing the integer n (1 ≤ n ≤ 500), the number of mountains, followed by the integer m (1 ≤ m ≤ 10000), the number of already installed antennas. The second line contains n integers h₁, h₂, . . . , h_n (h_i ∈ {50, 100}), respectively representing the height of the mountains on the base line from left to right. The third(last) line of the test case contains m integers specifying the position of the antennas already installed on the mountains. The position of each antenna is specified by its X coordinate, assuming the left-most point of the left-most mountain being the origin of the coordinate system. You yourself can calculate the Y coordinate of antenna as it is put on the boundaries of a mountain.

The input terminates with a line of the form ‘0 0’ which should not be processed as a test case.

Note: The Sample Input test case is related to the configuration illustrated in the above figure.

For each test case, write a single line containing the minimum number of extra wireless antennas needed for making the given set of antennas connected.