grid.in
grid.out
Peter prepared a rectangular sheet of grid paper for a math test. The sheet is N cells high and M cells wide (1 ≤ N,M ≤ 5000). Rows of the sheet are numbered downwards from 1 to N, and the columns left to right from 1 to M.
While waiting for the test to begin, Peter accidentally painted K different cells of his sheet (1 ≤ K ≤ 100,000, K < N∙M). Having received a warning from his teacher, Peter decided to cut out from this sheet a smaller rectangular block without painted cells.
Peter told his teacher that he knew the number of different ways to cut the block, but he does not. Help him!
The first line of the input file contains three numbers N, M, and K, separated by single spaces. Each of the following K lines describes one painted cell and contains two numbers separated by a space: the row and the column number of this cell.
The first and only line of the output file should contain a single integer - the total number of different ways a rectangular unpainted block may be cut out from the partially painted sheet.
Two blocks are considered different if there is at least one cell that belongs to one of the blocks and does not belong to the other one. The paper may be cut only along the lines separating cells from each other.
4 3 3 1 2 4 3 3 1
22