APM Automatic Color Minimization

CE Digital Company has developed an Automatic Painting Machine (APM) that paints a board composed of non-overlapping rectangles, each with a predetermined color (C_i). The machine works by picking up a brush of a certain color and painting all rectangles of that color that are eligible for painting. A rectangle (R_i) is eligible to be painted only if every rectangle immediately above it has already been painted. Formally, for every rectangle (R_j) such that (R_j.y_2 = R_i.y_1) and (\max(R_i.x_1, R_j.x_1) < \min(R_i.x_2, R_j.x_2)), rectangle (R_j) must have been painted before (R_i) can be painted. Note that when a brush is picked up, APM must paint every available rectangle of the corresponding color in one go (partial painting is not allowed). If the same brush is picked up more than once (even for the same color), every pickup is counted. Your task is to compute the minimum number of brush pickups required to paint all the rectangles under these constraints.

inputFormat

The first line contains an integer (n) ((1 \le n \le 15)), the number of rectangles. Each of the following (n) lines contains five integers: (x_1), (y_1), (x_2), (y_2), (c). Here, ((x_1, y_1)) is the top‐left coordinate and ((x_2, y_2)) is the bottom‐right coordinate of a rectangle, and (c) ((1 \le c \le 10)) represents its color. It is guaranteed that the rectangles do not overlap. A rectangle (R_i) can be painted only when for every rectangle (R_j) satisfying (R_j.y_2 = R_i.y_1) and (\max(R_i.x_1, R_j.x_1) < \min(R_i.x_2, R_j.x_2)), (R_j) has already been painted.

outputFormat

Output a single integer representing the minimum number of brush pickups required to paint all the rectangles.

sample

3
0 0 1 1 1
0 1 1 2 1
1 1 2 2 2

3