Problem1024--「一本通 1.3 练习 2」平板涂色

1024: 「一本通 1.3 练习 2」平板涂色

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

原题来自:POJ 1691

CE 数码公司开发了一种名为自动涂色机(APM)的产品。它能用预定的颜色给一块由不同尺寸且互不覆盖的矩形构成的平板涂色。

为了涂色,APM 需要使用一组刷子。每个刷子蘸了颜色 CCC 。APM 拿起一把蘸有颜色 CCC 的刷子,并给所有颜色为 CCC 的矩形涂色。请注意,涂色有顺序要求:为了避免颜料渗漏使颜色混合,一个矩形只能在所有紧靠它上方的矩形涂色后,才能涂色。例如图中矩形 FFF 必须在 CCCDDD 涂色后才能涂色。注意,每一个矩形必须立刻涂满,不能只涂一部分。

写一个程序求一个使 APM 拿起刷子次数最少的涂色方案。注意,如果一把刷子被拿起超过一次,则每一次都必须记入总数中。


Input

第一行为矩形的个数 NNN
下面有 NNN 行描述了 NNN 个矩形。每个矩形有 555 个整数描述,左上角的 yyy 坐标和 xxx 坐标,右下角的 yyy 坐标和 xxx 坐标,以及预定颜色。


Output

一行一个整数,表示拿起刷子的最少次数。


Sample Input

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

Sample Output

3

HINT

对于全部数据,1≤N≤141 \leq N \leq 141N14,颜色号为 111202020 的整数。保证平板的左上角坐标总是 (0,0)(0, 0)(0,0),坐标的范围是 000999


Source/Category


Submit Status