luogu#P1233. 木棍加工

木棍加工

题目描述

一堆木头棍子共有 nn 根,每根棍子的长度和宽度都是已知的。棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的:

  • 第一根棍子的准备时间为 11 分钟。
  • 如果刚处理完长度为 ll,宽度为 ww 的棍子,那么如果下一个棍子长度为 lil_i,宽度为 wiw_i,并且满足 llil\ge l_iwwiw\ge w_i,这个棍子就不需要准备时间,否则需要 11 分钟的准备时间。

计算处理完 nn 根棍子所需要的最短准备时间。比如,你有 55 根棍子,长度和宽度分别为 (4,9),(5,2),(2,1),(3,5),(1,4)(4,9),(5,2),(2,1),(3,5),(1,4),最短准备时间为 22(按 (4,9),(3,5),(1,4),(5,2),(2,1)(4,9),(3,5),(1,4),(5,2),(2,1) 的次序进行加工)。

输入格式

第一行是一个整数 nnn5000n\le5000)。

第二行是 2n2n 个整数,分别是 l1,w1,l2,w2,,ln,wnl_1,w_1,l_2,w_2,\ldots,l_n,w_nllww 的值均不超过 1000010000,相邻两数之间用空格分开。

输出格式

仅一行,一个整数,所需要的最短准备时间。

5
4 9 5 2 2 1 3 5 1 4

2

提示

对于 100%100 \% 的数据,1n50001 \le n \le 50001li,wi1041 \le l_i, w_i \le {10}^4