DEFKIN - Defense of a Kingdom

no tags 

Theodore implements a new strategy game “Defense of a Kingdom”. On each level a player defends the Kingdom that is represented by a rectangular grid of cells. The player builds crossbow towers in some cells of the grid. The tower defends all the cells in the same row and the same column. No two towers share a row or a column.

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

This position has a penalty of 12.

Help Theodore write a program that calculates the penalty of the given position.

Input

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

Each test case consists of a line with three integer numbers: w — width of the grid, h — height of the grid and n — number of crossbow towers (1 ≤ w, h ≤ 40 000; 0 ≤ n ≤ min(w, h)).

Each of the following n lines contains two integer numbers xi and yi — the coordinates of the cell occupied by a tower (1 ≤ xi ≤ w; 1 ≤ yi ≤ h).

Output

For each test case, output a single integer number — the number of cells in the largest rectangle that is not defended by the towers.

Example

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

Output:
12

hide comments
rishabh8485: 2018-03-10 01:10:02

Long Long - WA
int -AC
why?

nadstratosfer: 2017-08-26 00:12:38

Wasted an hour trying to think of a better solution than the one I designed as a test, then gave up and submitted for the hell of it; got the best time in Python. Listen to minhthai's advice =)

hacker: 2016-09-07 12:48:51

logical

GAURAV CHANDEL: 2016-08-23 19:30:13

1st implemented O(n*logn*logn) sol..(not worked for me)
2nd implemented O(n*logn) sol..........(not worked for me)
3rd implemented O(max(w,h)) sol.. (This was the easiest and it worked)...
Good Logical Problem...

vivu01: 2016-03-08 23:24:02

can be done in O(max(h,w))

codercool: 2016-02-01 21:10:14

width+1 and height+1

minhthai: 2016-01-30 11:38:59

be a simple coder :)

Last edit: 2016-01-30 11:39:17
anuveshkothari: 2015-12-14 08:59:17

really enjoyed solving it..O(n^2) TLE...O(nlogn) accepted...
not seeing @jaswanth comment costed me 3 WA's

Last edit: 2015-12-14 09:00:21
Jaswanth: 2015-08-14 04:13:42

check for case n=0 costed me 2 WA

Sahil Dua: 2014-11-04 09:19:30

Easier than what it looks like initially. O(nlogn) accepted :)


Added by:Fidel Schaposnik
Date:2010-11-08
Time limit:0.741s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM ICPC 2010, NEERC, Northern Subregional Contest