#P4211. 小港湾

小港湾

小港湾

题目描述

西瓜王 xgw 来到一个小港湾,想知道水能以多大的流量穿过港湾。

把水域看成一个宽 nn、长 mm 的网格。每个格子的坐标为 (x,y)(x,y),其中 0≤x<n0\le x<n,0≤y<m0\le y<m。水可以在共边的格子之间流动,每个没有被船坞占据的格子最多能通过 11 个单位的流量。船坞是与网格对齐的矩形,所占格子无法通水。

水从 y=0y=0 的一侧流入,从 y=m−1y=m-1 的一侧流出。求水域能通过的最大流量,即从起点侧到终点侧最多能有多少条互不共用格子的通路。

输入格式

第一行三个整数 n,m,kn,m,k,分别为水域宽度、长度和船坞数。

接下来 kk 行,每行四个整数 x0,y0,x1,y1x_0,y_0,x_1,y_1,表示该船坞覆盖所有满足 x0≤x≤x1x_0\le x\le x_1、y0≤y≤y1y_0\le y\le y_1 的格子。两对坐标所在的格子也被占据。

每个船坞位于水域内,任意两个船坞不共用格子。

输出格式

输出一个整数,表示最大流量。

样例 #1

样例输入 #1

5 6 4
1 0 1 0
3 1 3 3
0 2 1 3
1 5 2 5

样例输出 #1

2

样例说明

黑色格子表示船坞,蓝色格子表示可通水的水域。

样例水域及四个船坞的坐标

数据规模与约定

1≤n≤1 0001\le n\le1\,000,1≤m≤1081\le m\le10^8,0≤k≤2 0000\le k\le2\,000。