← 返回题目列表

Codeforces · 793/G

G. 奥列格和国际象棋

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

银行客户 Oleg 解决了一个有趣的国际象棋问题:在 n × n 棋盘上放置最大数量的车,这样它们就不会互相击败。当然,没有两个车可以共享同一个单元。

提醒,当且仅当 a = x 或 b = y 时,站在单元格 (a, b) 中的车击败站在单元格 (x, y) 中的车。

不幸的是(幸运的是?)对于奥列格来说,这个问题的答案始终是 n,所以这项任务很快就让奥列格感到无聊。他决定通过从板上移除一些单元来增加难度。如果一个单元格被删除,奥列格不能在那里放置一个车,但车确实可以“通过”删除的单元格互相击败。

Oleg 成组删除单元格,即反复选择一个边长与棋盘边平行的矩形,并删除该矩形内的所有单元格。形式上,如果他选择一个矩形,其左下单元格的坐标为 (x1, y1),右上角单元格的坐标为 (x2, y2),那么他将删除所有坐标为 (x, y) 且满足 x1 ≤ x ≤ x2 且 y1 ≤ y ≤ y2 的单元格。确保没有单元格被删除两次,即所选矩形不相交。

这个版本的问题奥列格无法解决,而他的朋友伊戈尔正忙于开会,所以他无法帮助奥列格。

你是奥列格最后的希望!帮助他:给定棋盘的大小和删除的矩形,找到可以放置在棋盘上的最大可能的车数量,以便没有两个车互相击败。

输入

第一行包含单个整数 n (1 ≤ n ≤ 10000) — 棋盘的大小。

第二行包含单个整数 q (0 ≤ q ≤ 10000) — 删除的矩形的数量。

接下来的 q 行包含有关删除的矩形的信息。

每行包含四个整数 x1、y1、x2 和 y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n) - 已删除矩形的左下和右上单元格的坐标。

如果保证矩形不相交。

输出

在唯一的一行中打印 Oleg 可以在棋盘上放置的车的最大数量,以便没有两个车互相击败。

示例

输入 #1

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

输出 #1

3

输入 #2

8
4
2 2 4 6
1 8 1 8
7 1 8 2
5 4 6 8

输出 #2

8

注意

这是棋盘和第一个示例中的车放置示例: