GIWED - The Great Indian Wedding
A wedding is to be organized in a rectangular park of dimensions M by N. Some parts of the park are covered by K rectangular carpets. These carpets, produced by ItSucks Corporation are revolutionary self cleaning carpets - they suck any liquid they come in contact with! The organizer wants to water the park to keep the grass fresh. If there were no carpets, the organizer could have used a single pipe to water the whole park but unfortunately, the water doesn't seep through the carpets. The organizer has at his disposal L pipes. The pipes would be placed at fixed locations chosen by the organizer and can't be moved. Water spreads from a pipe in all directions unless obstructed by the park boundary or a carpet. What is the maximum area that can be watered using these L pipes?
The first line of the input contains a single integer T, the number of test cases (1<=T<=30) . Each test case starts with a single line containing the values M, N, K and L (1<=M<=10000, 1<=N<=10000, 0<=K<=50, 1<=L<=10). It is followed by K lines, each line containing 4 integers separated by single spaces, x1, y1, x2, y2 where (x1, y1) and (x2, y2) are the zero based coordinates of lower left and upper right vertex of the carpet. Assume that x1 < x2 and y1 < y2. The carpets may cover each other. Water would not be able to seep through even if two carpets touch in a corner.
For each test case, print the maximum area that can be watered on a single line
Input: 2 10 10 0 1 10 10 1 1 3 3 4 4 Output: 100 99
Although probably (almost) obvious, it is not mentioned that M is related to the x-coordinate, and N to the y-coordinate.