Score : $600$ points

问题陈述

有一个 $H$ 行和 $W$ 列的网格。令 $(r, c)$ 表示从上到下第 $r$ 行、从左到右第 $c$ 列的方格。

我们有 $N$ 个棋子。对于第 $i$ 个棋子，我们可以选择执行以下操作之一：

• 将其放在满足条件 $A_i \leq r \leq C_i$ 和 $B_i \leq c \leq D_i$ 的方格 $(r, c)$ 上。
• 不将其放置在网格上。

但是，我们不能将两个棋子放在同一行或同一列中。

最多能在网格上放置多少个棋子？

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a grid with $H$ rows and $W$ columns. Let $(r, c)$ denote the square at the $r$-th row from the top and $c$-th column from the left.

We have $N$ pieces. For the $i$-th piece, we can choose to do one of the following:

• Put it at a square $(r, c)$ such that $A_i \leq r \leq C_i$ and $B_i \leq c \leq D_i$.
• Do not put it on the grid.

However, we cannot put two pieces in the same row or the same column.

At most how many pieces can we put on the grid?

Constraints

• $1 \leq H, W, N \leq 100$
• $1 \leq A_i \leq C_i \leq H$
• $1 \leq B_i \leq D_i \leq W$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$H$ $W$ $N$

$A_1$ $B_1$ $C_1$ $D_1$

$A_2$ $B_2$ $C_2$ $D_2$

$\vdots$

$A_N$ $B_N$ $C_N$ $D_N$

Output

Print the answer.

Sample Input 1

2 3 3
1 1 2 2
1 2 2 3
1 1 1 3

Sample Output 1

2

By putting the first piece at $(1, 1)$, the second piece at $(2, 2)$, and not putting the third piece on the grid, we can put two pieces on the grid. We cannot put three, so we should print $2$.

Sample Input 2

5 5 3
1 1 5 5
1 1 4 4
2 2 3 3

Sample Output 2

3

update @ 2024/3/10 09:18:54