나무 막대

면접 대비

시간 제한1초메모리 제한128 MB

요약

길이와 무게가 있는 막대 n개를 처리 순서를 정해 설치 시간의 합을 최소로 만든다. 직전 막대보다 길이와 무게가 모두 크거나 같으면 설치 시간이 들지 않는다.

난이도: 보통10점 중 5점
유형: 정렬, 그리디, 동적 계획법
정답자: 아직 제출이 없습니다

문제

목공소에 나무 막대 $n$ 개가 있고, 각 막대에는 길이와 무게가 정해져 있습니다. 막대들은 기계로 한 번에 하나씩 가공됩니다. 각 막대를 가공하기 전에는 기계를 그 막대에 맞게 준비시키는 시간, 즉 작동 준비 시간(setup time)이 필요할 수 있습니다. 작동 준비 시간은 다음 규칙으로 정해집니다.

맨 처음 막대를 가공할 때는 작동 준비 시간 1분이 필요합니다.
길이 $l$ , 무게 $w$ 인 막대를 가공한 직후에 길이 $l'$ , 무게 $w'$ 인 막대를 가공할 때, $l \le l'$ 이고 $w \le w'$ 이면 작동 준비 시간이 필요하지 않습니다. 그렇지 않으면 기계의 도구를 바꿔야 하므로 작동 준비 시간 1분이 필요합니다.

가공 순서는 자유롭게 정할 수 있습니다. 모든 막대를 가공하는 데 필요한 작동 준비 시간의 최솟값을 구하세요.

예를 들어 막대가 $(4,9), (5,2), (2,1), (3,5), (1,4)$ 다섯 개라고 합시다. $(1,4), (3,5), (4,9), (2,1), (5,2)$ 순서로 가공하면 작동 준비 시간이 모두 합쳐 2분이고, 이보다 더 줄일 수 없으므로 답은 2입니다.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어집니다.

각 테스트 케이스는 두 줄로 이루어집니다. 첫째 줄에는 나무 막대의 개수 $n$ ( $1 \le n \le 5000$ )이 주어집니다. 둘째 줄에는 $l_1\ w_1\ l_2\ w_2\ \dots\ l_n\ w_n$ 이 공백으로 구분되어 차례로 주어집니다. 여기서 $l_i$ 와 $w_i$ 는 각각 $i$ 번째 막대의 길이와 무게이며, 모두 $10000$ 이하의 정수입니다.

출력

각 테스트 케이스마다 필요한 작동 준비 시간의 최솟값을 한 줄에 하나씩 출력합니다.

예제1

예제 1

입력

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