题目描述

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.