SPOJ Problem Set (classical) 1672. The Great Indian Wedding Problem code: GIWED

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 unforunately, the water doesn't seep through the carpets. The organizer has at his diposal 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 containg 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₁,y₁,x₂,y₂ where (x₁,y₁) and (x₂,y₂) are the zero based coordinates of lower left and upper right vertex of the carpet. Assume that x₁<x₂ and y₁<y₂. 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:	1s
Source limit:	50000B
Languages:	All except: ERL TECS JS
Resource:	C-maphore, Tryst 2007