P1283 Board Painting

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.

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 a single integer, the minimum number of brush pickups.

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