/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
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) に置く
- 置かない
のいずれかを選択することができます。ここで、二つの駒が同じ行や同じ列に存在するような置き方をすることはできません。
最大で何個の駒を置くことができるでしょうか？
制約
- 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
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
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
出力
答えを出力せよ。
入力例 1
2 3 3 1 1 2 2 1 2 2 3 1 1 1 3
出力例 1
2
一つ目の駒をマス (1, 1) に、二つ目の駒をマス (2, 2) に置き、三つ目の駒は置かないようにすることで、2 個置くことができます。3 個置くことは不可能であるので、2 を出力します。
入力例 2
5 5 3 1 1 5 5 1 1 4 4 2 2 3 3
出力例 2
3
Score : 600 points
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