9456: Rectangle Intersection

In an $n$ by $m$ grid, there are $k$ rectangles, each described by a tuple $(x_1, y_1, x_2, y_2)$ ($1 \leq x_1 \leq x_2 \leq n, 1 \leq y_1 \leq y_2 \leq m$), indicating that the rectangle covers all cells from row $x_1$ to $x_2$ and from column $y_1$ to $y_2$. For a collection of rectangles, their intersection is defined as the set of all cells that are covered by all these rectangles simultaneously. If no cell is covered by all these rectangles simultaneously, we consider the intersection of these rectangles to be empty. Now, you need to select some rectangles from the given $k$ rectangles **such that their intersection is non-empty**, and you should **minimize** the number of cells contained in the intersection of these rectangles. You only need to output the number of cells contained in the intersection of these rectangles.

The first line of input contains three positive integers $n$, $m$, and $k$ ($1 \leq n, m \leq 2000, 1 \leq k \leq 10^6$), representing the number of rows and columns in the grid, and the number of rectangles, respectively. Then $k$ lines follow, each containing a description of one rectangle. Each rectangle's description consists of $4$ numbers $x_1, y_1, x_2, y_2$ ($1 \leq x_1 \leq x_2 \leq n, 1 \leq y_1 \leq y_2 \leq m$), indicating that the rectangle covers all cells from row $x_1$ to $x_2$ and from column $y_1$ to $y_2$.

Output a positive integer in a line, denoting the answer.

#### 示例2 ##### 输入 ``` 19 19 4 1 9 10 9 9 10 9 19 11 1 11 10 10 11 19 11 ``` ##### 输出 ``` 10 ``` #### 示例3 ##### 输入 ``` 7 7 2 1 1 7 7 2 2 6 6 ``` ##### 输出 ``` 25 ``` #### 示例4 ##### 输入 ``` 5 5 2 1 1 4 4 2 2 5 5 ``` ##### 输出 ``` 9 ```