题目描述
一堆木头棍子共有 n 根,每根棍子的长度和宽度都是已知的。棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的:
- 第一根棍子的准备时间为 1 分钟。
- 如果刚处理完长度为 l,宽度为 w 的棍子,那么如果下一个棍子长度为 li,宽度为 wi,并且满足 l≥li、w≥wi,这个棍子就不需要准备时间,否则需要 1 分钟的准备时间。
计算处理完 n 根棍子所需要的最短准备时间。比如,你有 5 根棍子,长度和宽度分别为 (4,9),(5,2),(2,1),(3,5),(1,4),最短准备时间为 2(按 (4,9),(3,5),(1,4),(5,2),(2,1) 的次序进行加工)。
输入格式
第一行是一个整数 n(n≤5000)。
第二行是 2n 个整数,分别是 l1,w1,l2,w2,…,ln,wn。l 和 w 的值均不超过 10000,相邻两数之间用空格分开。
输出格式
仅一行,一个整数,所需要的最短准备时间。
5
4 9 5 2 2 1 3 5 1 4
2
提示
对于 100% 的数据,1≤n≤5000,1≤li,wi≤104。