Closing Windows

Time limit1sMemory limit128 MB

Summary

Simulate closing overlapping windows in order to determine the minimum clicks needed to close the very first opened window whose top-right cell must become visible.

Level: Medium6 of 10
Topics: Simulation, Geometry, Greedy
Solved: No attempts yet

Problem

Several windows are open in order.

Each window is a rectangle made of 1 x 1 cells. A newly opened window may cover part or all of earlier windows depending on its position and size.

To close a window, you click its upper-right cell with the mouse. At the moment of the click, that cell must be visible. A cell of a window is visible if no later-opened window that has not yet been closed covers that cell.

Find the minimum number of mouse clicks needed to close the window that was opened first.

Input

The first line contains an integer N, the number of windows. 1 <= N <= 100.

Each of the next N lines contains four integers R1, S1, R2, and S2 separated by spaces. 1 <= R1 <= R2 <= 10000 and 1 <= S1 <= S2 <= 10000. The pair (R1, S1) is the row and column of the upper-left cell of that window, and (R2, S2) is the row and column of the lower-right cell. The windows are opened in the same order as they appear in the input.

Think of the screen as rows and columns of small cells. Row numbers increase from top to bottom, column numbers increase from left to right, and the upper-left cell of the screen is in row 1 and column 1.

Output

Print one integer: the minimum number of mouse clicks needed to close the window that was opened first.

Examples3

Example 1
Input
```
3
3 1 6 4
1 2 4 6
2 3 5 5
```
Expected output
```
3
```
Example 2
Input
```
3
4 1 6 3
2 2 5 5
1 4 3 6
```
Expected output
```
3
```
Example 3
Input
```
3
3 3 4 4
1 1 2 2
5 5 6 6
```
Expected output
```
1
```