网格与棋子

题目描述

有一个 $H$ 行 $W$ 列的网格。将从上方数第 $r$ 行、从左侧数第 $c$ 列的格子记作 $(r,c)$。

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

• 将其放在满足 $A_i \le r \le C_i$ 且 $B_i \le c \le D_i$ 的格子 $(r,c)$ 上。
• 不把它放在网格上。

但是，不能有两个棋子放在同一行或同一列。

最多可以放置多少个棋子？

输入格式

输入按以下格式从标准输入给出：

$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$

输出格式

输出答案。

样例

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

2

将第 1 个棋子放在 $(1,1)$，第 2 个棋子放在 $(2,2)$，不放置第 3 个棋子，则可以放置 2 个棋子。

无法放置 3 个棋子，因此输出 $2$。

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

3

数据范围

• $1 \le H, W, N \le 100$
• $1 \le A_i \le C_i \le H$
• $1 \le B_i \le D_i \le W$
• 输入均为整数