← 返回题目列表

AtCoder · abc205_f

F. 网格和代币

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有一个网格 H 行和 W 列。让 (r, c) 表示位于 r从顶部数第行和 c左起第 列。

我们有 N 件。对于 i- 第一块,我们可以选择执行以下操作之一:

  • 把它放在一个正方形上 (r, c) 这样 A_i \leq r \leq C_i 和 B_i \leq c \leq D_i.
  • 请勿将其放在网格上。

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

我们最多可以在网格上放置多少块?

约束

  • 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.


示例输入 2

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

示例输出 2

3