#x1062. CF1198E Rectangle Painting 2

    ID: 5975 远端评测题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-二分图建模顶点覆盖离散化二维差分最小割建模Dinic最大流最小割定理二分图最小点覆盖2500

CF1198E Rectangle Painting 2

Rectangle Painting 2

题面翻译

有一个n∗nn*n的网格,网格中有一些点是黑的,其他点都是白的。你每次可以花费min⁡(h,w)\min(h,w)的代价把一个h∗wh*w的矩形区域变白。求把所有黑格变白的最小代价。

输入格式

第一行2个整数nn,mm(1≤n≤109,0≤m≤501\le n \le 10^9,0\le m\le 50),分别代表正方形网格的大小和黑色矩形的数量。

接下来mm行,每行44个整数xi1,yi1,xi2,yi2x_{i1},y_{i1},x_{i2},y_{i2}($1\le x_{i1}\le x_{i2}\le n,1\le y_{i1}\le y_{i2}\le n$),分别代表黑色矩形左下角的格子和右上角的格子。(显然,黑色矩形里的格子都是黑的。)

黑色矩形可能相交。

输出格式

一个整数:把所有格子变白的最小代价。

题目描述

There is a square grid of size n×n n \times n . Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs min⁡(h,w) \min(h, w) to color a rectangle of size h×w h \times w . You are to make all cells white for minimum total cost.

The square is large, so we give it to you in a compressed way. The set of black cells is the union of m m rectangles.

输入格式

The first line contains two integers n n and m m ( 1≤n≤109 1 \le n \le 10^{9} , 0≤m≤50 0 \le m \le 50 ) — the size of the square grid and the number of black rectangles.

Each of the next m m lines contains 4 integers xi1 x_{i1} yi1 y_{i1} xi2 x_{i2} yi2 y_{i2} ( 1≤xi1≤xi2≤n 1 \le x_{i1} \le x_{i2} \le n , 1≤yi1≤yi2≤n 1 \le y_{i1} \le y_{i2} \le n ) — the coordinates of the bottom-left and the top-right corner cells of the i i -th black rectangle.

The rectangles may intersect.

输出格式

Print a single integer — the minimum total cost of painting the whole square in white.

样例 #1

样例输入 #1

10 2
4 1 5 10
1 4 10 5

样例输出 #1

4

样例 #2

样例输入 #2

7 6
2 1 2 1
4 2 4 3
2 5 2 5
2 3 5 3
1 2 1 2
3 2 5 3

样例输出 #2

3

提示

The examples and some of optimal solutions are shown on the pictures below.