G  Palace of King

All submissions for this problem are available.
A king in a distant land wants to build a new palace for himself. There are some plots of land in the country. Some of them don't have any owner, some of the plots are owned by the citizens of the country. Being a good person, the king wants to pay the appropriate amount of money for the land he uses. If he uses some portion of a plot, he needs to buy the whole plot. Also, this is a weird country where the plots owned by the citizens may overlap. For an area, the king needs to buy all the overlapping plots to use that area. To use some area not owned by any citizen, the king doesn't need to spend any money.
Formally, the country is an M × N grid with L plots owned by the citizens. Each of these plots is rectangular in shape. The i^{th} plot has its lower left corner at (x_{i}, y_{i}), length l_{i} (along with the xaxis), width w_{i} (along with the yaxis), and price p_{i}. The palace the king is going to build should be rectangular in shape as well. Please help him to find the rectangular place with the largest area which he can use without spending more than C amount of money.
(0,0) is the lower left corner of the country and (M, N) is the upper right corner. All the plots owned by the citizens are inside this area. The palace should be inside this area as well. The sides of the palace should be axisparallel.
Input
 The first line of the input contains an integer T denoting the number of test cases. Description of each test case is given below.
 The first line of each test case contains three integers M, N, and C.
 The second line contains L.
 Each of next L lines contains the description of a plot owned by a citizen. i^{th} of these line has five integers: x_{i}, y_{i}, l_{i}, w_{i}, and p_{i}.
Output
For each test case, print "Case i: ", and then the answer (mod 10^{9} + 7), where i is the testcase number, 1indexed. The answer should be the largest area of the rectangular shaped land that can be used without spending more than C amount of money.
Constraints
 1 ≤ T ≤ 10
 1 ≤ M, N ≤ 1000
 0 ≤ C ≤ 1000000000
 0 ≤ x_{i} ≤ M  l_{i}
 0 ≤ y_{i} ≤ N  w_{i}
 1 ≤ l_{i}, w_{i}
 1 ≤ p_{i} ≤ 100000
 1 ≤ L ≤ 1000
Example
Input: 1 4 4 6 3 1 0 2 1 2 2 0 1 4 2 0 3 3 1 4 Output: Case 1: 12
Explanation
The image above shows the lands owned by the citizens and the palace with area 12 (lower left corner at (0,0) and upper right corner at (4,3)).
Author:  zubaerkh 
Tags  zubaerkh 
Date Added:  20112017 
Time Limit:  8 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 