Description

CE Digital has developed a product called the Automatic Painting Machine (APM). It can paint a board composed of non-overlapping rectangles of various sizes using predetermined colors.

To paint, the APM uses a set of brushes. Each brush paints a distinct color $C_i$. The APM picks up a brush of color $C_i$ and paints all rectangles whose color is $C_i$ and which satisfy the restriction below:

To prevent paint from seeping and mixing colors, a rectangle can be painted only after all rectangles that are immediately above it have been painted. For example, in the figure, rectangle $F$ can be painted only after $C$ and $D$ have been painted. Note that each rectangle must be painted to completion immediately; you cannot paint only part of it.

Write a program to find a painting plan that minimizes the number of times the APM picks up a brush. Note that if a brush is picked up more than once, each pickup counts toward the total.

Input Format

The first line contains the number of rectangles $N$. The next $N$ lines each describe one rectangle. Each rectangle is given by $5$ integers: the top-left $y$-coordinate and $x$-coordinate, the bottom-right $y$-coordinate and $x$-coordinate, and the predetermined color.

The top-left coordinate of the board is always $(0, 0)$.

Output Format

Output a single integer, the minimum number of brush pickups.

7
0 0 2 2 1
0 2 1 6 2
2 0 4 2 1
1 2 4 4 2
1 4 3 6 1
4 0 6 4 1
3 4 6 6 2

3

Hint

Constraints: $1 \le C_i \le 20$, $0 \le x_i, y_i \le 99$, $1 \le N \le 16$.

Translated by ChatGPT 5