Maximizing Manhattan Distance Sum in a Grid Cafeteria

In a cafeteria, the seating is arranged in a rectangular grid divided into ( n \times m ) cells, where the rows are numbered from 1 to ( n ) and the columns from 1 to ( m ). Each cell ( (i,j) ) with ( 1 \le i \le n,,1 \le j \le m ) represents a seat. Currently, there are ( k ) people sitting at given positions ( (x_i, y_i) ) for ( 1 \le i \le k ). The person sxz wants to choose a seat ( (a,b) ) (which must not be occupied by any one of the ( k ) people) such that the total Manhattan distance [ D(a,b)=\sum_{i=1}^{k}\left(|a-x_i|+|b-y_i|\right) ] is maximized. Your task is to help sxz find this maximum possible distance sum.

Note: It is obvious that sxz cannot choose a seat already occupied by one of the ( k ) people.

inputFormat

The first line contains three integers ( n, m, k ) ( (1 \le n, m;, k \ge 1) ) representing the number of rows, columns, and people, respectively. Each of the following ( k ) lines contains two integers ( x_i ) and ( y_i ) ( 1 \le x_i \le n,, 1 \le y_i \le m ) indicating the seat coordinates occupied by a person.

outputFormat

Output a single integer: the maximum possible sum of Manhattan distances between sxz's chosen seat and the ( k ) occupied seats.

sample

3 3 4
1 1
1 3
3 1
3 3

8