题目描述

$H$ 行 $W$ 列のグリッドがあり、上から $r$ 行目、左から $c$ 列目のマスを $(r,\ c)$ と表します。

$N$ 個の駒があり、$i\ \,\ (1\ \leq\ i\ \leq\ N)$ 個目の駒に対しては

• $A_i\ \leq\ r\ \leq\ C_i$ かつ $B_i\ \leq\ c\ \leq\ 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$

输出格式

答えを出力せよ。

题目大意

你有一个 $H$ 行 $W$ 列的方格，通过 $(r,c)$ 表示第 $r$ 行第 $c$ 列的单元格。

你又有 $n$ 枚棋子，对第 $i$ 枚棋子，你可以选择以下一个操作：

• 将这枚棋子放在 $(r,c)$，满足 $A_i \le r \le C_i, B_i \le c \le D_i$
• 跳过这枚棋子，即不放到棋盘上并处理下一枚棋子。

我们不允许最后在某一行或某一列上有超过一枚棋子。在此条件下，你最多可以放多少枚棋子？

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

2

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

3

提示

制約

• $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$
• 入力は全て整数である。

Sample Explanation 1

一つ目の駒をマス $(1,\ 1)$ に、二つ目の駒をマス $(2,\ 2)$ に置き、三つ目の駒は置かないようにすることで、$2$ 個置くことができます。$3$ 個置くことは不可能であるので、$2$ を出力します。