c++ - What's a good algorithm for Defense of a Kingdom? -

i trying solve defense of kingdom problem , came algorithm exceeds time limit of problem.

i want know algorithm solve within time limit.

the problem:

theodore implements new strategy game “defense of kingdom”. on each level player defends kingdom represented rectangular grid of cells. player builds crossbow towers in cells of grid. tower defends cells in same row , same column. no 2 towers share row or column.

the penalty of position number of cells in largest undefended rectangle. example, position shown on picture has penalty 12.

help theodore write program calculates penalty of given position.

input

the first line of input file contains number of test cases.

each test case consists of line 3 integer numbers: w — width of grid, h — height of grid , n — number of crossbow towers (1 ≤ w, h ≤ 40 000; 0 ≤ n ≤ min(w, h)).

each of following n lines contains 2 integer numbers xi , yi — coordinates of cell occupied tower (1 ≤ xi ≤ w; 1 ≤ yi ≤ h).

output

for each test case, output single integer number — number of cells in largest rectangle not defended towers.

example

input:
1
15 8 3
3 8
11 2
8 6

output: 12

i this:

given w, h width , height of playing field, , coordinates of towers (x1,y1) .. (xn,yn), split coordinates 2 lists x1..xn, y1..yn, sort both of coordinate lists.

then calculate empty spaces, e.g. dx[] = { x1, x2-x1, ..., xn - xn-1, (w + 1) - xn }. same y coordinates: dy[] = { y1, y2-y1, ..., yn - yn-1, (h + 1) - yn }. multiply max(dx)-1 max(dy)-1 , should have largest uncovered rectangle. have decrement delta values 1 because line covered higher coordinate tower included in it, not uncovered.