Sum of Manhattan Distances on a Grid with Obstacles

A game map is represented by an \( n \times m \) grid. There are \( k \) obstacles located on distinct grid points. The distance between two adjacent grid points is 1. At the beginning of the game, three players: L, W, and H are spawned on the grid. They each spawn independently at a random grid point that is not an obstacle.

Player L is curious about the total distance between the birth positions of players W and H over all possible spawn arrangements. Here the distance between two grid points \( A=(x_1,y_1) \) and \( B=(x_2,y_2) \) is defined as the Manhattan distance: \( |x_1-x_2| + |y_1-y_2| \). Note that the pair \( (A,B) \) is considered the same as \( (B,A) \); hence, only unordered pairs are counted.

Your task is to calculate the sum of Manhattan distances over all unordered pairs of valid spawn positions for players W and H.

Hint: Let the set of valid points (i.e. grid points without an obstacle) be \( S \). For each row \( i \), define \( r_i \) as the number of valid points in that row; similarly, for each column \( j \), define \( c_j \) as the number of valid points in that column. Then the answer can be computed as the sum of two parts:

[ \text{Answer} = \sum_{1 \le i < j \le n} (j-i), r_i, r_j + \sum_{1 \le p < q \le m} (q-p), c_p, c_q. ]

inputFormat

The first line contains three integers \( n \), \( m \) and \( k \) representing the number of rows, columns and the number of obstacles respectively. Each of the next \( k \) lines contains two integers \( r \) and \( c \) (1-indexed) representing the row and column of an obstacle.

outputFormat

Output a single integer: the sum of Manhattan distances between every unordered pair of valid spawn positions for players W and H.

sample

3 3 2
1 1
2 2

44