스케줄

시간 제한2초메모리 제한512 MB

요약

구간 작업들을 기계에 배정하되 겹치는 작업은 같은 기계에 둘 수 없다. 기계 수를 최소로 하고, 그때 각 기계의 가동 시간(가장 이른 시작부터 가장 늦은 종료까지) 합을 최소로 구한다.

난이도: 어려움10점 중 8점
유형: 구간, 그리디, 정렬, 힙
정답자: 아직 제출이 없습니다

문제

$N$ 개의 작업이 있다. $i$ 번째 작업은 $s_i$ 시각에 시작해서 $e_i$ 시각에 끝나야 한다. 기계는 얼마든지 많이 쓸 수 있다. 각 작업은 기계 하나에 배정된다. 한 기계는 배정된 작업들이 서로 겹치지 않기만 하면 몇 개든 처리할 수 있다. 작업 $i$ 와 $j$ 가 겹친다는 것은 열린 구간 $(s_i, e_i)$ 와 $(s_j, e_j)$ 의 교집합이 비어 있지 않다는 뜻이다.

기계는 배정된 작업 중 가장 이른 시작 시각에 켜지고, 가장 늦은 종료 시각에 꺼진다. 기계의 작동 시간은 이 두 시각 사이 구간의 길이이다. 기계 하나를 켰다 껐다 하는 것은 한 번뿐이다.

모든 작업을 처리하는 데 쓸 수 있는 기계의 최소 개수 $K$ 를 구하라. 또 기계 $K$ 개를 쓸 때 작동 시간의 합의 최솟값을 구하라.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다 ( $1 \le T \le 100$ ).

각 테스트 케이스의 첫 줄에는 정수 $N$ 이 주어진다 ( $0 < N \le 10^5$ ). 다음 $N$ 개 줄에 정수 $s_i$ 와 $e_i$ 가 주어진다 ( $0 \le s_i < e_i \le 10^9$ ).

$N > 50$ 인 테스트 케이스는 10개를 넘지 않는다.

출력

각 테스트 케이스마다 한 줄에 정수 두 개를 출력한다. 모든 작업을 처리하는 데 필요한 기계의 최소 개수 $K$ 와, 기계 $K$ 개를 쓸 때 작동 시간 합의 최솟값이다.

예제1

예제 1
입력
```
1
3
1 3
4 6
2 5
```
예상 출력
```
2 8
```