#2334 Pickup Game

10 s   128 MB  


You are playing a computer game called the "Pickup." The rules are as follows: 

  1. There are a number of horizontal and vertical line segments. (See the figure below.) 
  2. You can "Pickup" a pair of line segments by clicking on the crossing made by the pair. (The pair disappears from screen when you do this.) 
  3. Each line segment is given a weight. 
  4. When you pick up a pair with weights a and b, you are given a score of a × b.

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. 

Sample Input

Sample Output

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


[Problem ] Daejeon Nationalwide Internet Competition 2013 [Judge I/O data] mitslll