#1257. 木棒

木棒

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

现有n根木棒,已知它们的长度和重量。要用一部木工机一根一根地加工这些木棒。该机器在加工过程中需要一定的准备时间,是用于清洗机器,调整工具和模板的。木工机需要的准备时间如下:

  • 1)第一根木棒需要1min的准备时间;
  • 2)在加工了一根长为l\red{l},重为w\red{w}的木棒之后,接着加工一根长为ll\red{ll}l<=ll\red{l<=ll}),重为ww\red{ww}w<=ww\red{w<=ww})的木棒是不需要任何准备时间的。否则需要一分钟的准备时间。 给定n根木棒,你要找到最少的准备时间。例如现在有长和重分别为(4\red{4},9\red{9}),(5\red{5},2\red{2}),(2\red{2},1\red{1}),(3\red{3},5\red{5})和(1\red{1},4\red{4})的五根木棒,那么所需准备时间最少为2min,顺序为(1\red{1},4\red{4}),(3\red{3},5\red{5}),(4\red{4},9\red{9}),(2\red{2},1\red{1}),(5\red{5},2\red{2})。

输入格式

输入包含多组测试数据。输入的第一行是一个整数T\red{T},表示测试数据的个数。 每个测试例两行: 第一行是一个整数n\red{n}1<=n<=5000\red{1<=n<=5000}),表示有多少根木棒; 第二行包括n2\red{n*2}个整数,表示了l1\red{l_1}w1\red{w_1}l2\red{l_2}w2\red{w_2}l3\red{l_3}w3\red{w_3},...,ln\red{l_n}wn\red{w_n},这些数均不大于10000\red{10000},其中li\red{l_i}wi\red{w_i}表示第i\red i根木棒的长度和重量。

输出格式

输出以分钟为单位的最少准备时间。

样例

输入样例

3 
5 
4 9 5 2 2 1 3 5 1 4 
3 
2 2 1 1 2 2 
3 
1 3 2 2 3 1

输出样例

2
1
3

寒假营测试2

未参加
状态
已结束
规则
ACM/ICPC
题目
6
开始于
2022-1-14 14:00
结束于
2022-1-15 14:00
持续时间
24 小时
主持人
参赛人数
18