## 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?

### Input

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, x_{1}, y_{1}, x_{2}, y_{2}
where (x_{1}, y_{1})
and (x_{2}, y_{2}) are the zero
based coordinates of lower left and upper right vertex of the carpet.
Assume that x_{1} < x_{2 }and y_{1} < y_{2}.
The carpets may cover each other. Water would not be able to
seep through even if two carpets touch in a corner.

### Output

For each test case, print the maximum area that can be watered on a single line

### Example

Input:2 10 10 0 1 10 10 1 1 3 3 4 4Output:100 99

hide comments

amaroq:
2009-05-25 15:13:43
Although probably (almost) obvious, it is not mentioned that M is related to the x-coordinate, and N to the y-coordinate. |

Added by: | Rahul Garg |

Date: | 2007-07-04 |

Time limit: | 0.100s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |

Resource: | C-maphore, Tryst 2007 |