8 10 s 128 MB
You are playing a computer game called the "Pickup." The rules are as follows:
Figure 1. An Example Screen
The first goal is to pick up the most line segments. The second goal is to maximize the total score. That is, if there are more than one way of picking up the most line segments, then you have to find the one with the largest possible score.
Write a program, given the specification of an instance of the game, which computes the maximum possible number of line segments that can be picked up and the maximum possible score.
Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with integers n and m, the number of horizontal and vertical line segments, respectively, where 1 ≤ n, m ≤ 200. Each of the following n lines contains five integers x,y,x',y',w, representing the two endpoints (note, y = y′) and the weight of each horizontal line segment. Also each of the following m lines contains an analogous information for each vertical line segment. All coordinate values are positive and are less than or equal to 100,000. The weights are also positive and are less than or equal to 20. Any pair of line segments may share at most one point which is never an endpoint of the line segments.
Your program is to write to standard output. Print exactly one line containing two integers for each test case. You should output the maximum possible number of line segment pairs that can be picked up, followed by maximum possible score while picking up the most pairs of line segments.
2 2 2 1 2 4 2 1 1 3 4 3 2 2 1 2 4 3 3 1 3 4 4 2 2 1 2 5 2 3 7 2 6 2 3 2 3 2 1 2 3 1 3 3 1
2 11 1 6