#P4211. 小港湾
小港湾
小港湾
题目描述
西瓜王 xgw 来到一个小港湾,想知道水能以多大的流量穿过港湾。
把水域看成一个宽 、长 的网格。每个格子的坐标为 ,其中 ,。水可以在共边的格子之间流动,每个没有被船坞占据的格子最多能通过 个单位的流量。船坞是与网格对齐的矩形,所占格子无法通水。
水从 的一侧流入,从 的一侧流出。求水域能通过的最大流量,即从起点侧到终点侧最多能有多少条互不共用格子的通路。
输入格式
第一行三个整数 ,分别为水域宽度、长度和船坞数。
接下来 行,每行四个整数 ,表示该船坞覆盖所有满足 、 的格子。两对坐标所在的格子也被占据。
每个船坞位于水域内,任意两个船坞不共用格子。
输出格式
输出一个整数,表示最大流量。
样例 #1
样例输入 #1
5 6 4
1 0 1 0
3 1 3 3
0 2 1 3
1 5 2 5
样例输出 #1
2
样例说明
黑色格子表示船坞,蓝色格子表示可通水的水域。

数据规模与约定
,,。