Minimum Rectangle Covering of Bare Cells

Lili and Nana have been weeding in the backyard. The backyard is modeled as a 2D grid where each cell represents one unit area. They performed a total of \(n\) operations. In the \(i\)th operation they clear (remove grass from) all cells inside the rectangle \([l_i, r_i] \times [b_i, t_i]\). Note that these rectangles may overlap.

After these operations the union of the cleared (bare) cells constitutes one or more orthogonal polygons (with all sides horizontal or vertical). Some of these polygons may not be connected and may even have holes. Later, Lili and Nana want to plant different plants in several rectangles (which do not overlap) so that the union of these rectangles exactly covers all the bare cells. Of course, Lili – being fond of polygons – wants the number of such rectangles to be as small as possible.

Example. For instance, if there are two operations with the first rectangle given by \([1,5]\times[2,3]\) and the second by \([2,3]\times[1,4]\) (note that here the rectangle \([l, r]\times[b, t]\) covers all cells with x coordinate between \(l\) and \(r\) (inclusive) and y coordinate between \(b\) and \(t\) (inclusive)), one possible optimal covering is by three non‐overlapping rectangles: \([1,1]\times[2,3]\), \([2,3]\times[1,4]\) and \([4,5]\times[2,3]\).

Your task is to compute the minimum number of non–overlapping rectangles required to exactly cover all the bare cells.

Note on coordinates: In each operation, the rectangle \([l, r]\times[b, t]\) covers every cell \((x,y)\) with \(l \le x \le r\) and \(b \le y \le t\). Even if the original cleared area is huge, the boundaries come only from the given operations so that the bare region can be compressed into a small grid.

Input/Output specification: See below.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10\)), the number of weeding operations.

Each of the next \(n\) lines contains four integers \(l_i\), \(b_i\), \(r_i\), and \(t_i\) (\(-10^9 \le l_i \le r_i \le 10^9\), \(-10^9 \le b_i \le t_i \le 10^9\)), describing an operation. The rectangle defined by \([l_i, r_i]\times[b_i, t_i]\) indicates that all cells with coordinates \(x,y\) satisfying \(l_i \le x \le r_i\) and \(b_i \le y \le t_i\) are cleared.

outputFormat

Output a single integer: the minimum number of non–overlapping rectangles needed to cover exactly all the bare cells.

sample

1
1 1 1 1

1