#216671. [GKS 2018 #D] Paragliding

In order to advance in his quest to defeat the villainous Graphendorf, our hero Edge has to overcome a challenge in a shrine. The shrine is two-dimensional in the xy-plane, and there are towers (of varying heights) erected along the x-axis of the plane. Each tower can be represented by a vertical line segment in a 2D plane. For tower , the base of the tower is at , and the top of the tower is at . There are also balloons floating in the plane. Each balloon can be represented by a single point in the 2D plane, with balloon at position . Edge has to collect as many balloons as possible in this challenge.

Fortunately, Edge has a trusty paraglider which he found in a different room of this shrine. He may choose to climb any tower and glide down from any position on the tower towards either the positive or negative direction of the x-axis. When he glides, he descends in a straight path that makes a 45 degrees angle relative to the tower. Edge can collect any balloons in his way when he glides down from the tower. He can repeat this process of climbing up a tower and jumping off any number of times. If he touches a tower during his descent, then he is considered to be on the tower at the point and climbing. You may assume Edge to be a single point in the xy-plane.

Using a pair of goggles made from ancient technology, Edge was able to figure out the height and position of each tower and balloon. With this information, can you help Edge deduce the maximum number of balloons that he can collect in this shrine?

The first line of the input gives the number of test cases, . test cases follow. Each test case contains five lines. The first line contains the integers and as described above. Each of the next four lines describe a recurrence used to generate the positions and heights of the towers and the and coordinates of the balloons. The four lines will each contain six integers in the following format:

To generate the values for (from 3 to N), (from 3 to N), (from 3 to K) and (from 3 to K), we use the following recurrences:

• , for to N.
• , for to N.
• , for to K.
• , for to K.

It is guaranteed that no two towers share the same position. However, it is possible for a tower to overlap with a balloon. In this case, we assume that the balloon can be collected. Note that two or more balloons might share a point; in that case, Edge can collect all of those balloons at once by passing through that point.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and is the maximum number of balloons that Edge can collect.

样例输入 1

2
3 2
1 4 1 1 0 11
4 1 1 1 8 11
2 5 0 0 0 11
4 1 0 0 0 11
5 5
2 4 1 0 1 13
4 4 0 1 12 13
1 4 1 1 0 13
3 5 1 1 7 13

样例输出 1

Case #1: 1
Case #2: 4

Note that the input for Sample Case #1 produces the scenario depicted in the problem statement. The generated arrays are:

• .
• .
• .
• .

In Sample Case #2, the generated arrays are:

• .
• .
• .
• .

Limits

.

for to .

for to .

for to .

for to .

.

.

.

.

for to , .

Small dataset (Test set 1- Visible)

.

.

Large dataset (Test set 2 - Hidden)

.

.