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, 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.

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 4

Output:
100
99

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

hide comments
2009-05-25 15:13:43 amaroq
Although probably (almost) obvious, it is not mentioned that M is related to the x-coordinate, and N to the y-coordinate.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.